[알고리즘] 다익스트라 알고리즘(Dijkstra's algorithm)

다익스트라 알고리즘은 그래프에서 정점 간의 최단 경로를 찾는 알고리즘이다.
기본적으로 단일 출발(single source) 최단 경로 문제를 다룰 수 있다.

다익스트라 알고리즘은 항상 정점 주변의 최단 경로만을 선택하는 그리디(Greedy) 알고리즘 중 하나이다.
정점을 출발 집합에 추가할 때, 그 정점까지의 최단 경로는 이미 계산되었다는 확신을 갖는다.

정점 주변을 탐색할 때에는 너비 우선 탐색(BFS)을 이용한다.
따라서 출발 정점으로부터 다른 모든 정점에 도달할 수 있다면 O(E log V), 그렇지 않은 경우 O((V+E) log V)가 소요된다.

가중치가 음수인 간선이 하나라도 존재하면 다익스트라 알고리즘을 적용할 수 없다는 단점이 있다.
그러나 현실 세계에는 그러한 간선이 존재하지 않으므로 자주 채택되는 알고리즘이다.

가중치가 음수인 간선이 포함된 경우, 벨만-포드 알고리즘(Bellman–Ford algorithm)을 활용할 수 있다.

구현 [Python]

사실 최초 다익스트라 알고리즘은 O(N^2)에 구현되었지만, 현재는 정점으로부터 놓인 최단 경로를 찾을 때 우선순위 큐(Priority Queue)를 이용함으로써 위에서 살펴본 것처럼 O(N log N)으로 개선되었다.

import collections

data = {
    (0, 1, 3), (0, 3, 4), (0, 4, 1),
    (1, 2, 5), (3, 2, 2), (4, 3, 2)
}
graph = collections.defaultdict(list)
for u, v, w in data:
    graph[u].append((v, w))

def dijkstra(start: int) -> list[int]:
    heap = [(0, start)]
    dist = [float("inf")] * (n + 1)
    dist[start] = 0

    while heap:
        path_len, node = heapq.heappop(heap)
        if dist[node] < path_len:
            continue
        for (link, length) in graph[node]:
            alt = path_len + length
            if alt < dist[link]:
                dist[link] = alt
                heapq.heappush(heap, (alt, link))

>>> dijkstra(0)
[0, 3, 5, 3, 1]