알고리즘[최단경로] 다익스트라(Dijkstra)

개요

다익스트라 최단 경로 알고리즘은 그래프 상의 어떤 노드에서 출발해 다른 특정 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.
이 때의 그래프는 음의 값을 가지는 간선이 없을 때 정상적으로 동작하며 현실에서는 음의 간선으로 표현되지 않으므로 GPS에도 이용된다고 한다.

다익스트라 알고리즘의 원리는

1. 출발 노드의 설정
2. 최단 거리 테이블 초기화
3. 방문하지 않은 노드 중 비용이 가장 낮은 노드 선택
4. 3. 에서의 노드를 거쳐 다른 노드로 가는 비용으로 최단 거리 테이블 갱신
5. 3과 4의 반복  

과 같이 이뤄져있다.

과정 중 3.을 통해 다익스트라 최단거리 알고리즘은 그리디 알고리즘의 한 종류로 분류되어진다.

다익스트라의 구현에는 구현하기 편하지만 성능이 보장되지 않는 구현 방법과 구현하기에 다소 불편하나 성능이 보장되는 구현 방법이 있다.

(1) 구현 용이, 성능 보장되지 않는 다익스트라

import sys
input = sys.stdin.readline
INF = int(1e9)
# 노드, 간선 개수
n,m = map(int,input().split())
# 탐색 시작 노드
start = int(input())
# 노드 정보 그래프
graph = [[] for i in range(n+1)]
# 방문 여부
v = [0] * (n+1)
# 간선에 대한 최단 거리 테이블
dist = [INF] * (n+1)
for _ in range(m):
    #a와 b가 연결된 간선, 간선의 비용
    a, b, c = map(int, input().split())
    graph[a].append((b,c))

def get_smallest_node():
    min_val = INF
    index = 0
    for i in range(1, n+1):
        if dist[i] < min_val and not v[i]:
            min_val = dist[i]
            index = i
    return index

def dijkstra(start):
    dist[start] = 0
    v[start] = 1

    for j in graph[start]:
        dist[j[0]] = j[1]

    for i in range(n-1):
        now = get_smallest_node()
        v[now] = 1
        for j in graph[now]:
            cost = dist[now] + j[1]
            if cost < dist[j[0]]:
                dist[j[0]] = cost
dijkstra(start)

for i in range(1, n+1):
    if dist[i] == INF:
        print("can't reach")
    else:
        print(dist[i])

(2) 구현 불편, 성능 보장 다익스트라

import heapq,sys

input = sys.stdin.readline

INF = int(1e9)
# 노드, 간선 개수
n,m = map(int,input().split())
# 탐색 시작 노드
start = int(input())
# 노드 정보 그래프
graph = [[] for i in range(n+1)]
# 간선에 대한 최단 거리 테이블
distance = [INF] * (n+1)

for _ in range(m):
    #a와 b가 연결된 간선, 간선의 비용
    a,b,c = map(int,input().split())
    graph[a].append((b,c))

def dijkstra(start):
    q = []
    heapq.heappush(q,(0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost,i[0]))
dijkstra(start)
for i in range(1, n+1):
    if distance[i] == INF:
        print("can't reach")
    else:
        print(distance[i])

두 구현 방법에서 성능 차이의 가장 큰 이유는 (1) 에서는 가장 낮은 cost를 가지는 노드를 찾기 위해 선형 탐색을, (2) 에서는 heapq를 사용하고 있다는 점이다.

선형 탐색을 이용하게 된다면 노드의 개수 $O(V)$번에 걸쳐 그에 따른 가장 짧은 노드를 매번 선형 탐색해야하기 때문에 시간복잡도 $O(V^2)$이 걸리게 된다.

반면 우선순위큐 즉 heapq를 이용하여 구현한다면 시간 복잡도 $O(ElogV)$로 큰 차이를 보이게 된다. 이는 다익스트라 알고리즘은 최대 간선의 개수만큼의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 유사하기 때문이다.

이렇듯 두 구현 방법에는 명확한 성능 차가 존재한다. 따라서 코딩테스트 등에서 입력이 크게 제한된 상황이 아니라면 heapq를 사용하는 (2)를 사용하는 것이 좋겠다.