다익스트라(Dijkstra) 알고리즘은 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘이다. 다익스트라 알고리즘의 시간복잡도는 O(E)+O(ElogE)=O(ElogE)이다.
다익스트라 알고리즘에서는 방문하지 않은 인접 노드를 탐색할 때 우선순위 큐를 사용한다. 그 이유는 지금까지 발견된 가장 가까운 거리의 노드를 먼저 계산할 수 있기 때문이다. 가장 가까운 정점을 계산해 놓으면 그보다 더 먼 거리의 경로에 대해서는 고려할 필요가 없어진다. 우선순위 큐는 heapq
모듈을 이용해 구현할 수 있다.
a
라면, distance[b] = a->b의 거리
를 뜻함)0
으로 초기화한다.len(우선순위 큐) > 0
), 큐에서 꺼내 해당 정점에서 방문하지 않은 인접 정점들을 탐색한다.distance[a]
)보다 현재 정점을 거쳐 인접 정점에 도달하는 거리가 더 짧을 경우 짧은 거리로 갱신해준다.
시작점이 A
일 때, d[A]
만 0
으로 놓고 나머지는 무한대로 설정한다. S
는 방문한 노드의 집합이고, Q
는 방문하지 않는 노드의 집합이다. 파이썬 코드에서는 Q
를 우선순위 큐로 거리까지 함께 저장해 사용할 것이다.
시작점 A
의 인접 정점들을 탐색하며, d[노드]
에 저장되어 있는 값보다 정점 A
를 거쳐 가는 값이 더 작을 경우 그 값으로 업데이트한다. 여기서는 모두 INF 무한대 값보다 작기 때문에 연결된 인접 정점을 모두 업데이트하게 된다.
정점 B
의 인접 정점들을 탐색한다. 역시 무한대 값보다 무조건 작기 때문에 d[E]
를 업데이트하게 된다.
계속해서 방문하지 않은 노드가 없을 때까지 반복해준다. 현재 정점을 거쳐 인접 정점으로 가는 것이 더 비용이 적게 들 때 d
리스트의 값을 업데이트해준다. 그림에서는 정점 C
로 갈 때, 시작점 A
에서 바로 C
로 가는 것(30
)보다 A -> D -> C
를 거쳐서 가는 것(20
)이 더 빠르기 때문에 d[C]
를 업데이트해 주었다. 마찬가지로 A -> C -> F
보다 A -> D -> C -> F
가 더 빠르기 때문에 d[F]
값을 업데이트해 주었다.