[자료구조][알고리즘] Dijkstra's Algorithm(다익스트라 알고리즘)

1. Dijkstra's Algorithm이란?

Dijkstra's Algorithm(다익스트라 알고리즘)은 각 edge에 cost가 있는 direct graph에서 한 vertex에서 출발하여 다른 모든 vertex까지 도달하는 최단 경로를 찾는 알고리즘(Single Source All Destination)이다. 이때 최단 경로는 거치는 edge들의 cost 합이 최소인 경우를 의미한다. 다익스트라 알고리즘을 n번 사용하면 모든 vertex의 다른 모든 vertex에 대한 최단 경로(All-Pairs Shortest Paths)를 찾을 수 있다.
다익스트라 알고리즘은 모든 edge의 cost가 0보다 크거나 같을 때에만 최단 경로임이 보장되므로, 만약 cost가 음수인 edge가 있다면 다익스트라 알고리즘 대신 Bellman-Ford Algorithm(벨먼-포드 알고리즘)이나 Floyd-Warshall Algorithm(플로이드-워셜 알고리즘)을 사용해야 한다.(플로이드-워셜 알고리즘은 음의 cycle이 있는 경우 최단 경로를 보장하지 않으므로, 벨먼-포드 알고리즘을 권장한다.)

2. 예시

위와 같은 그래프가 있을 때, 1에서 출발하여 다른 vertex까지 도달하는 최단 경로를 구하고자 한다. $d$는 해당 vertex까지의 거리(cost 합), $p$는 해당 vertex까지 도달하기 바로 전의 vertex를 의미한다.
1에서 출발하였으므로, 1까지의 거리는 0, 이전 노드는 없다.

1과 연결된 edge들을 탐색하며, 1에서 도달할 수 있는 노드들의 거리를 갱신한다. 2의 $d$는 6, 3의 $d$는 2, 4의 $d$는 16, 7의 $d$는 14로 갱신되었다. 또, 이 노드들의 이전 노드를 1로 갱신하였다.

이렇게 거리가 갱신된 노드 중 가장 거리가 짧은 3에서 출발하여 다른 노드들의 거리를 갱신할 것이다. 3에서 도달 가능한 5, 6 노드의 거리를 갱신하였다. 이때 갱신하는 거리들은 3까지의 $d$에 3에서 5, 6 노드까지의 edge의 cost를 더하여 갱신된다. 5, 6 노드의 이전 노드도 3으로 갱신하였다.

그리고, 3 노드 다음으로 cost가 작은 5 노드에서 출발하여 거리를 갱신한다. 이때 5에서 나오는 edge의 cost와 5까지의 cost의 합이 기존 $d$보다 작은 경우에만 갱신한다. 따라서 4 노드의 $d$는 기존 16에서 5의 $d$에 4를 더한 9가 된다. 이전 노드도 5로 갱신된다.

5 노드 다음으로 cost가 작은 2 노드에서 나오는 edge들을 이용해 각 노드까지의 cost를 계산했을 때, 2 노드에서 도달 가능한 4, 5 노드의 경우 새로운 $d$가 이전 $d$보다 크기 때문에, 갱신하지 않는다.
다음으로, 4 노드의 edge들을 이용해 cost를 계산했을 때, 7 노드까지의 $d$가 기존 $d$보다 작으므로, 이를 갱신한다. 이전 노드도 4로 갱신해준다.

그리고 4 노드 다음으로 cost가 작은 6 노드에서 나오는 edge들을 이용해 각 노드까지의 cost를 계산했을 때, 7 노드까지의 $d$가 기존 $d$보다 작으므로, 이를 갱신한다. 이전 노드도 6으로 갱신해준다.
이러한 방식으로 오름차순으로 모든 노드의 cost를 확인하고 갱신하면, 1 노드에서 모든 노드까지의 최단 경로를 구할 수 있다.

3. 시간 복잡도

• Single Source All Destination
  • 인접 행렬 또는 인접 리스트 사용: $O(n^2)$
  • Min heap 사용 시: $O((n+e)\log n)$
  • Fibonacci heap 사용 시: $O(n\log n + e)$
• All-Pairs Shortest Paths: $O(n^3)$