다익스트라 알고리즘 1 — 각 정점까지의 최단 거리만 구하기

“지금까지 거리를 확정한 정점들 중에서, 가장 가깝게 닿을 수 있는 다음 정점을 하나씩 추가한다.” 다익스트라는 그리디 알고리즘이고, 매 단계 정점을 고르는 방식이 Prim과 많이 닮았다. 차이가 있다면 Prim은 “트리에 가장 가볍게 붙는 간선”를 보고, Dijkstra는 “시작점에서 거리가 가장 짧은 정점”을 본다는 점이다. Prim과의 본격적인 비교는 2편에서 다룬다.

알고리즘의 아이디어

입력은 가중 그래프 $G = (V, E, w)$와 시작점 $v_0$이고, 정점(vertex) 수는 $n$이다. 이 글은 그래프의 점을 정점, 이음선을 간선(edge) 으로 부른다. 여기서 도착점은 따로 정하지 않는다. 임의의 정점 $v_n$까지의 최단 경로를 구하면 그 경로 위에 있는 모든 중간 정점까지의 최단 거리도 자동으로 함께 얻어지기 때문이다. 만약 중간의 어떤 부분 경로가 최단이 아니었다면, 그 부분을 더 짧은 경로로 바꿔서 전체 길이를 줄일 수 있을 텐데, 이는 모순이다. 그래서 처음부터 모든 정점까지의 거리를 한꺼번에 구한다.

각 정점 $u$에 대해 현재까지 추정한 최단 거리 $d_{min}(u)$를 관리한다. 초깃값은 다음과 같다.

• 간선 $(v_0, u)$가 존재하면: $d_{min}(u) = w(v_0, u)$
• 간선이 없으면: $d_{min}(u) = \infty$

그리고 이미 답이 확정된 정점들의 집합 $R$을 도입한다. 처음에는 $R = \{v_0\}$이다. 시작점까지의 거리는 당연히 $0$이다.

이제 $R$이 모든 정점을 포함할 때까지 다음 세 단계를 반복한다.

1. $R^C$(아직 확정되지 않은 정점들) 중 $d_{min}$이 가장 작은 정점 $u$를 고른다.
2. $u$를 $R$에 추가한다. 이 시점에 $d_{min}(u)$가 $u$의 진짜 최단거리로 확정되는데, 왜 그런지는 아래 정확성 증명에서 다룬다.
3. $u$에서 나가는 간선을 따라 $R^C$에 있는 인접 정점 $v$들의 거리를 $d_{min}(v) = \min(d_{min}(v),\ d_{min}(u) + w(u, v))$로 갱신한다.

---

Pseudo-code

// G = (V, E, w), 시작 정점 v0
R       = { v0 }
d[v0]   = 0
d[v]    = ∞                    for all v ≠ v0
d[v]    = w(v0, v)             if (v0, v) ∈ E

while (R != V) {
    u = argmin { d[u] : u ∉ R };
    R = R ∪ { u };
    for each (u, v) ∈ E with v ∉ R {
        d[v] = min(d[v], d[u] + w(u, v));
    }
}
return d;

한 번의 반복은 정점 하나를 $R$에 추가한다. 시작할 때 $|R| = 1$이고 끝났을 때 $|R| = n$이므로, 반복은 정확히 $n - 1$번 일어난다.

이 글은 두 가지 가정 위에서 이야기를 풀어간다. 첫째로 모든 간선 가중치가 $0$ 이상이고, 둘째로 시작점 $v_0$에서 모든 정점에 도달할 수 있다고 본다. 음의 가중치나 도달 불가능한 정점을 처리하는 방법은 후속 글에서 다룬다.

---

단계별 진행 시각화

작은 그래프 한 개로 알고리즘을 따라가 보자.

• 정점: $A, B, C, D, E$ (시작점 $A$)
• 간선: $A{-}B(2),\ A{-}C(5),\ B{-}C(1),\ B{-}D(7),\ C{-}D(3),\ C{-}E(8),\ D{-}E(2)$

각 단계에서 선택된 정점은 빨간색으로 채워지고, 그 정점이 갱신한 간선은 굵은 빨간색이 된다. 단계별 변화를 표로 정리하면 다음과 같다.

반복	선택된 $u$	$R$ (추가 후)	갱신된 $d_{min}$ 값들
1	$B$	$\{A, B\}$	$d[C]: 5 \to 3$, $d[D]: \infty \to 9$
2	$C$	$\{A, B, C\}$	$d[D]: 9 \to 6$, $d[E]: \infty \to 11$
3	$D$	$\{A, B, C, D\}$	$d[E]: 11 \to 8$
4	$E$	$\{A, B, C, D, E\}$	—

이 그림에서 볼 수 있듯이, Dijkstra는 항상 가까운 정점부터 추가한다. $d_{min}$ 값이 작은 순서대로 $R$에 들어간다는 뜻이다.¹

---

정확성 증명

Dijkstra가 매 단계 올바른 정점을 $R$에 추가한다는 것, 그리고 그때 갱신하는 간선만으로 모든 거리가 정확히 유지된다는 것을 두 명제로 나누어 증명한다.

1. 가장 작은 $d_{min}(u)$가 정말 $u$의 최단거리인가

알고리즘은 $R^C$ 중 $d_{min}$이 가장 작은 정점 $u$를 골라 $R$에 추가하면서 “$d_{min}(u)$가 $u$의 최단거리”라고 선언한다. 이게 왜 맞을까?

가정. $d_{min}(u)$가 $u$의 최단거리가 아니라고 해 보자. 그러면 이보다 더 짧은 어떤 경로 $P$가 존재할 것이다. 그런데 현재 $d_{min}(u)$는 “$R$의 정점들만 거쳐서 $u$에 도달하는 최단 길이”이므로, $P$는 반드시 어딘가에서 $R$ 바깥으로 빠져나간다. 그렇게 처음으로 $R^C$에 들어가는 정점을 $u'$이라고 하자.

관찰. $u'$ 역시 $R^C$의 원소다. 그러니 $u$를 고른 조건(가장 작은 $d_{min}$)에 의해

$$d_{min}(u) \le d_{min}(u')$$

이 성립한다. 또한 경로 $P$가 $u'$에 도달하는 시점의 누적 길이는 이미 $d_{min}(u')$ 이상이다. $d_{min}(u')$이 “$R$만 거쳐 $u'$에 도달하는 최단 길이”로 정의되기 때문이다.

결론. 따라서 $P$의 전체 길이는

$$|P| \ge d_{min}(u') \ge d_{min}(u)$$

가 된다. 이는 $P$가 $d_{min}(u)$보다 짧다는 가정에 모순이다. 그러므로 $d_{min}(u)$는 곧 $u$의 최단거리다.

	주장
가정	$d_{min}(u)$가 $u$의 최단거리가 아니다 → 더 짧은 경로 $P$ 존재
관찰	$P$는 어느 순간 $R^C$로 빠짐 → 첫 진입점 $u' \in R^C$ 존재
관찰	$u$는 $R^C$ 중 가장 작은 $d_{min}$을 가지므로 $d_{min}(u) \le d_{min}(u')$
결론	$\lvert P \rvert \ge d_{min}(u') \ge d_{min}(u)$ → 모순

2. 왜 새로 추가된 $u$의 간선만 갱신해도 충분한가

알고리즘은 $u$를 $R$에 추가한 직후, $u$에서 직접 나가는 간선만 가지고 $R^C$의 거리를 갱신한다. $R$ 안에 있는 다른 정점들은 다시 들여다보지 않는다. 이렇게만 해도 왜 충분할까?

의문. $u$를 거쳐 다시 $R$ 안의 어떤 정점 $t$를 들렀다가, 거기서 $R^C$의 정점 $v$로 빠지는 경로는 왜 따로 고려하지 않아도 될까?

관찰. $t$는 $u$보다 먼저 $R$에 들어온 정점이다. 이미 $R$에 있다는 건 그 시점에 $t$의 거리가 확정됐다는 뜻이다. 그때 정해진 $d_{min}(t)$는 $u$를 거치지 않고 얻은 길이다. 따라서

$$d_{min}(t) \le \underbrace{d_{min}(u) + w(u, t)}_{u \text{를 거쳐 } t \text{로 가는 경로 길이}}$$

가 성립한다. 만약 이게 성립하지 않는다면 $t$의 거리가 더 줄어들 수 있었다는 말이고, 이는 $d_{min}(t)$가 진짜 최단거리라는 사실과 모순이다.

결론. 그러므로 $u \to t \to v$ 경로의 길이는

$$d_{min}(u) + w(u, t) + w(t, v) \ge d_{min}(t) + w(t, v)$$

가 된다. 그런데 $d_{min}(t) + w(t, v)$는 $t$가 $R$에 들어왔을 때 이미 $v$를 갱신하면서 반영된 값이다. 즉 새로운 정보가 아니다. 그래서 $u$를 거쳐 $t$로 우회하는 경로는 굳이 볼 필요가 없고, $u$에서 $v$로 직접 가는 간선만 새로 갱신하면 충분하다.

Footnotes

1. 이 사실의 정식 증명은 후속 글에서 다룬다. 알고리즘이 추가하는 순서대로 $d_{min}$이 단조증가한다는 것을 보이면 된다. ↩