Overview

만약 서울에서 부산까지 최단 거리를 구하고 싶다면 어떻게 구할 수 있을까? 물론 도로를 생각하지 않으면 모든 벽을 뚫고 지나가는 Euclidean Distance가 가장 가깝겠지만…

Shortest Path Algorithm에는 대표적으로 Dijkstra’s Algorithm, Bellman-Fold Algorithm이 있다.

Shortest Path

Shortest Path(최단 경로)는 Weighted Directed Graph 위에 있는 source(출발점) $s$에서 destination(도착점) $t$까지의 최단 경로를 구하는 문제이다.

• Shortest path에 v가 포함되어 있다면,
  • $v$는 한 번만 포함될 것이다. 그러지 않고 cycle이 생기면 길이만 늘어날 뿐이다.
  • $s$에서 $v$까지 경로는 shortest path여야 한다.
  • $v$에서 $t$까지 경로는 shortest path여야 한다.

Negative Cycles

만약 가중치가 음수라면, cycle에 갇히게 될 수 있으며 전체 길이가 줄어들 수 있다. 그렇게 된다면 shortest path를 구할 수 없을 것이다.

Relaxation

Relaxation은 $v$에 대한 최단 거리 $d[v]$를 업데이트하는 과정이다. 이를 통해 발견된 최단 거리를 유지할 수 있다.

Dijkstra’s Algorithm

Dijkstra’s Algorithm(다익스트라 알고리즘)은 모든 가중치가 양수일 때 사용할 수 있으며, $s$와 다른 모든 vertex 간 shortest path를 제공한다.

과정

1. P[A][B]를 A와 B 사이의 거리라고 가정한다.
2. 출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 inf를 채워 넣는다.
3. 현재 노드를 나타내는 변수 A에 출발 노드의 번호를 저장한다.
4. A로부터 갈 수 있는 임의의 노드 B에 대해, (d[A] + P[A][B])와 d[B]의 값을 비교한다.
5. 만약 d[A] + P[A][B]의 값이 더 작다면, d[B]의 값을 이 값으로 relax한다.
6. A의 모든 이웃 노드 B에 대해 이 작업을 수행한다.