다익스트라 알고리즘 2 — 최단 경로 복원, 시간 복잡도, 그리고 Prim과의 비교

1편에서는 시작점 $v_0$에서 각 정점까지의 최단 거리, 그러니까 “길이”만 구했다. 그런데 거리를 알아도 정작 어떤 길로 가야 그 거리가 나오는지는 모른다. 2편에서는 그 경로를 직접 복원하는 방법을 본다. 더불어 이 알고리즘이 실제로 얼마나 빠른지($O(m \log n)$), 그리고 Prim과는 뭐가 같고 뭐가 다른지까지 정리한다.

세 가지 변형

다익스트라는 무엇을 출력하느냐에 따라 크게 세 가지로 나눌 수 있다.

1. 각 정점까지의 최단 거리(길이)만 계산한다. 1편에서 다룬 내용이다.
2. 거리뿐 아니라 그 거리를 만든 경로까지 복원한다. 이번 글의 주제다.
3. 한 정점까지 가는 모든 최단 경로를 찾는다. 2번을 조금만 확장하면 된다.

세 경우 모두 알고리즘의 뼈대는 1편과 같다. 간단히 되짚어 보면,

• 답이 확정된 정점 집합 $R$을 $\{v_0\}$에서 시작해 하나씩 키운다.
• 매 단계 아직 확정되지 않은 정점($R^C$) 중 $d_{min}$이 가장 작은 정점 $u$를 골라 $R$에 넣는다.
• 그런 다음 $u$에서 나가는 간선으로 이웃 정점 $v$의 거리를 갱신한다.

$$d_{min}(v) = \min\big(d_{min}(v),\ d_{min}(u) + w(u, v)\big)$$

2편에서 새로 하는 일은 딱 하나다. 이 거리 갱신이 일어날 때, 누가 갱신했는지를 같이 적어 두는 것이다.

---

최단 경로 복원

거리만 가지고 있으면 “A에서 E까지 8”이라는 것은 알아도, 정작 어떤 길을 거쳐서 8이 됐는지는 알 수 없다. 경로를 되살리는 방법은 의외로 간단하다. 각 정점이 자기 바로 앞 정점(부모, predecessor) 하나만 기억하고 있으면 된다.

갱신 규칙에 한 줄만 덧붙이면 된다.

• $u$가 $v$의 거리를 갱신했다면(즉 $d_{min}(u) + w(u,v)$가 더 짧았다면), $v$는 부모로 $u$를 기억한다.
• 두 경로 길이가 같다면, 두 정점을 모두 기억한다. (이 경우는 아래에서 다룬다.)

각 정점은 바로 앞 정점 하나만 가리킬 뿐이지만, 그래프 전체를 놓고 보면 이 부모 포인터들이 모여서 시작점 $v_0$을 뿌리로 하는 트리가 된다(동률이 없는 경우). 그래서 어떤 정점의 최단 경로가 궁금하면, 그 정점에서 부모를 따라 거꾸로 올라가다가 $v_0$에 닿으면 그게 곧 경로다.

1편의 예제 그래프를 그대로 가져오면, 갱신 과정에서 기록된 부모는 다음과 같다.

정점	최단거리 $d_{min}$	부모	누가 언제 갱신했나
$A$	$0$	—	시작점
$B$	$2$	$A$	$A$를 $R$에 넣을 때
$C$	$3$	$B$	$B$ 추가 시 $5 \to 3$
$D$	$6$	$C$	$C$ 추가 시 $9 \to 6$
$E$	$8$	$D$	$D$ 추가 시 $11 \to 8$

$E$에서 부모를 거꾸로 따라가면 $E \to D \to C \to B \to A$가 되고, 이걸 뒤집으면 최단 경로 $A \to B \to C \to D \to E$(길이 8)가 나온다.

---

모든 최단 경로 — DAG

이 절은 모든 가중치가 양수($w > 0$)라고 두고 읽는다. $0$이 섞이면 아래 방식이 무너지는데, 그 이야기는 절 끝에서 따로 한다.

최단 거리가 같은 경로가 둘 이상 있을 수도 있다. 거리를 갱신하려는데 새 경로의 길이가 기존 $d_{min}(v)$와 정확히 같다면, 기존 부모를 덮어쓰지 말고 둘 다 저장한다. 이렇게 하면 한 정점이 부모를 여러 개 가질 수 있게 되고, 부모 포인터들의 모임은 더 이상 트리가 아니라 DAG(방향 비순환 그래프)가 된다.

위 그림에서 $D$까지 거리 $3$으로 가는 경로는 $A \to B \to D$와 $A \to C \to D$, 이렇게 둘이다. $D$가 부모로 $B$와 $C$를 둘 다 기억해 두면, $D$에서 부모를 거슬러 올라가는 모든 갈래가 그대로 $D$의 모든 최단 경로가 된다. 결국 시작점 $v_0$을 뿌리로 하는 최단경로 DAG가 만들어지는 셈이다.

비순환이 보장되는 이유. 거리 갱신은 언제나 이미 $R$에 확정된 정점이 일으킨다. 그러니 어떤 정점 $v$의 부모로 기록되는 정점은 항상 $v$보다 먼저 확정된 정점이다. 부모 간선이 늘 “먼저 확정된 정점 → 나중에 확정된 정점” 방향으로만 생기므로 부모 포인터에 사이클이 생기지 않는다.

가중치 $0$이 섞이면

앞의 비순환 논거는 $w = 0$이어도 그대로 성립한다. 그런데 빠짐없음이 깨진다. 확정된 정점은 더 갱신하지 않기 때문이다.

세 정점 $s$, $a$, $b$에 간선 $s ext{–}a$, $s ext{–}b$, $a ext{–}b$가 모두 가중치 $0$인 그래프를 보자. 세 정점의 거리가 모두 $0$이다. 확정 순서가 $s, a, b$였다고 하면 이렇게 된다.

• $a$를 확정할 때 $b$를 보고 $0 + 0 = 0$이 $d_{min}(b)$와 같으므로 $b$의 부모에 $a$를 더한다.
• $b$를 확정할 때 $a$를 보지만, $a$는 이미 $R$에 있어 갱신하지 않는다.

그래서 $a$의 부모는 $s$ 하나뿐이고, DAG에서 나오는 $a$까지의 경로는 $s o a$ 하나다. 그런데 $s o b o a$도 길이 $0$인 최단 경로다. 하나를 놓친다.

그렇다고 이미 확정된 정점까지 갱신하면 $a$의 부모에 $b$가, $b$의 부모에 $a$가 들어가 부모 포인터에 사이클이 생긴다. $0$ 가중치에서는 비순환과 빠짐없음을 이 방식으로 동시에 얻을 수 없다.

$0$을 허용하면서 모든 최단 경로를 원한다면 순서를 바꾸면 된다. 먼저 거리 $d_{min}$을 전부 구한 다음, 그 값을 써서 $d_{min}(u) + w(u, v) = d_{min}(v)$를 만족하는 간선 $(u, v)$를 모두 모으는 것이다. 다만 이렇게 모은 그래프는 $0$ 가중치가 만드는 같은 거리 정점들 사이에서 사이클을 가질 수 있어 DAG가 아니다. 그때는 그 사이클 덩어리를 하나로 묶어 다뤄야 한다.

---

시간 복잡도

1편 의사코드에서 가장 비싼 부분은 ”$R^C$ 중 $d_{min}$이 가장 작은 $u$를 찾는다”는 argmin이었다. 매번 전체를 훑으면 한 번에 $O(n)$이고, 이걸 $n$번 가까이 반복하니 다 합치면 $O(n^2)$이 된다. 여기서 우선순위 큐(최소 힙)를 쓰면 훨씬 빨라진다.

비용을 두 부분으로 나눠서 세어 보자.

• 거리 갱신(간선 relax): 각 간선은 양 끝점이 $R$에 들어갈 때 많아야 한 번씩만 검사된다. 그래서 갱신은 전부 합쳐 $O(m)$번 일어나고, 한 번 갱신할 때마다 우선순위 큐를 손보는 데 $O(\log n)$이 드니, 합치면 $O(m \log n)$이다.
• 최솟값 추출: $R$이 한 정점씩 커지면서 $n - 1$번 반복하는데, 매번 큐에서 가장 작은 $d_{min}$을 꺼내는 데 $O(\log n)$이 든다. 합치면 $O(n \log n)$이다.

둘을 더하면 $O\big((n + m)\log n\big)$인데, 시작점에서 모든 정점에 갈 수 있다는 전제라면 $m \ge n - 1$이므로 그냥

$$O(m \log n)$$

으로 정리된다.

그런데 여기서 짚어 둘 게 하나 있다. $O(m \log n)$이 $O(n^2)$보다 항상 빠른 건 아니다. 결국 간선 수 $m$이 얼마냐에 달려 있다.

간선이 적은 희소(sparse) 그래프라면 $m$은 $n$ 정도라서, $O(m \log n)$이 사실상 $O(n \log n)$이고 $O(n^2)$보다 훨씬 빠르다. 우선순위 큐를 쓰는 이유가 바로 여기에 있다. 반대로 간선이 빽빽한 밀집(dense) 그래프에서는 $m$이 $n^2$에 가까워진다. 그러면 $O(m \log n)$은 $O(n^2 \log n)$이 되어, 오히려 단순 배열로 argmin을 선형 탐색하는 $O(n^2)$ 구현이 더 낫다. $\log n$만큼 손해를 보는 셈이다.

그래서 우선순위 큐는 만능 최적화가 아니라, “간선이 적당히 적을 때” 빛을 보는 도구다. 다만 실전에서 마주치는 그래프는 대부분 희소한 편이라, 힙 기반 구현이 기본 선택으로 자리 잡았다.

방금 “큐를 손보는 데 $O(\log n)$“이라고 했는데, 이 부분은 구현에 따라 조금 달라진다. 감소 키(decrease-key)를 지원하는 힙을 써서 거리를 직접 줄여도 되지만, 실제로는 더 단순한 lazy deletion 방식을 많이 쓴다. 거리가 줄어들 때마다 (새 거리, 정점)을 큐에 새로 push 해 버리고, 나중에 큐에서 꺼낸 항목의 거리가 지금 $d_{min}$과 다르면(이미 더 짧은 값으로 확정된 정점이라는 뜻이다) 그냥 버리는 것이다. 이러면 한 정점이 큐에 여러 번 들어갈 수 있지만, 큐 크기가 $O(m)$을 넘지 않기 때문에 전체 복잡도는 여전히 $O(m \log n)$이다.

---

BFS로부터의 아이디어

다익스트라가 가까운 정점부터 차례로 퍼져나가는 걸 보면 BFS가 떠오른다. 사실 BFS도 일종의 최단거리 알고리즘인데, 모든 간선의 가중치를 1이라고 본 경우라고 생각하면 된다.

그렇다면 가중치가 있는 그래프도 BFS로 풀 수 있지 않을까? 가중치가 양의 정수라고 하면 가능하다. 가중치가 $w$인 간선을 더미 정점 $w - 1$개로 쪼개서, 길이 1짜리 간선 $w$개로 바꾸면 된다. 그러면 모든 간선의 가중치가 1이 되니 BFS를 그대로 돌려도 최단거리가 나온다. 다만 이 분해는 가중치가 양의 정수일 때만 통한다. 다익스트라 자체는 $0$이나 실수 가중치도 처리하지만, BFS로 바꾸는 트릭은 그보다 조건이 까다롭다.

BFS는 시작점에서 한 겹씩 바깥으로 퍼져나가고, 어떤 정점에 처음 도달했을 때까지 거쳐 온 간선의 수가 곧 그 정점까지의 최단거리가 된다. 문제는 가중치가 커지면 더미 정점이 폭발적으로 많아져서 그래프가 거대해지고, 그만큼 느려진다는 점이다. 다익스트라는 이 “한 칸씩 퍼지는 BFS”를 거리 갱신으로 압축한 버전이라고 볼 수 있다. 더미 정점을 일일이 밟고 지나가는 대신, $d_{min}$ 값 하나로 “몇 칸 떨어져 있는지”를 한꺼번에 관리하는 것이다.

---

가까운 정점부터 추가된다

1편에서는 그림으로 관찰만 하고 증명은 뒤로 미뤄 둔 사실이 하나 있었다. 다익스트라가 항상 $d_{min}$이 작은 정점부터 $R$에 넣는다는 것, 다시 말해 정점이 추가되는 순서대로 $d_{min}$ 값이 단조증가한다는 것이다. 이제 이걸 증명해 보자.

확정되는 정점을 순서대로 $u_1 = v_0, u_2, u_3, \cdots$라고 하자. 연달아 확정되는 두 정점 $u_i$와 $u_{i+1}$에 대해 $d_{min}(u_i) \le d_{min}(u_{i+1})$이 성립한다는 것만 보이면 충분하다. 이웃한 쌍마다 성립하면 전체 순서의 단조성은 추이적으로 따라오기 때문이다.

그 전에 한 가지 짚어 둘 게 있다. 어떤 정점 $v$의 거리는 $u_i$가 갱신한 뒤에도, 이후에 확정되는 또 다른 정점 $x$ 때문에 다시 줄어들 수 있다. 그래서 “$u_i$가 직접 갱신한 경우”만 따지면 부족하고, 그사이에 $v$의 거리를 건드릴 수 있는 정점이 누구인지까지 봐야 한다.

• 확정 시점 비교. $u_i$를 확정하던 순간에 $u_{i+1}$은 아직 $R^C$에 남아 있었다(더 나중에 확정되니까). 가장 작은 거리를 고르는 argmin 규칙 때문에, 그 시점 $u_{i+1}$의 잠정 거리는 이미 $d_{min}(u_i)$ 이상이다.
• 그사이의 갱신. 거리 갱신은 오직 방금 $R$에 들어간 정점만 일으킨다. 그런데 $u_i$가 확정된 다음 $u_{i+1}$이 확정되기 전까지 새로 $R$에 들어간 정점은 $u_i$ 하나뿐이다. 따라서 이 구간에서 $u_{i+1}$의 거리를 건드릴 수 있는 건 $u_i$에서 나가는 간선밖에 없다. 그 갱신값은

$$d_{min}(u_i) + w(u_i, u_{i+1}) \ge d_{min}(u_i) \qquad (w \ge 0)$$

이므로 이것도 $d_{min}(u_i)$ 이상이다.

두 경우 모두 잠정 거리가 $d_{min}(u_i)$ 이상이니, $u_{i+1}$이 최종적으로 확정될 때의 거리도 $d_{min}(u_i)$ 이상이다. 즉 $d_{min}(u_i) \le d_{min}(u_{i+1})$이다. 이게 이웃한 모든 쌍에서 성립하므로, 추가되는 순서대로 $d_{min}$은 절대 줄어들지 않는다. 결국 다익스트라는 가까운 정점부터 차례로 확정하는 것이다.

핵심은 이렇다. 어떤 정점이든 자기보다 먼저 확정된 정점한테만 갱신을 받고, 그 먼저 확정된 정점의 거리는 (귀납적으로) 더 작을 수가 없다. 앞에서 말한 $x$가 $v$를 나중에 다시 갱신하더라도, $x$ 역시 $v$보다 먼저 확정된 정점이기 때문에 $w \ge 0$ 아래에서는 $v$의 거리를 $d_{min}(u_i)$ 밑으로 끌어내리지 못한다.

사실 이 단조성은 앞에서 본 우선순위 큐가 제대로 동작하는 근거이기도 하다. 한 번 큐에서 꺼내 확정한 정점의 거리를 나중에 다시 줄일 일이 없으니, 안심하고 확정해도 되는 것이다.

---

Prim vs Dijkstra

Prim과 다익스트라는 “지금 가장 좋아 보이는 정점을 트리에 하나씩 붙여 나간다”는 그리디 골격이 똑같다. 코드로 써 봐도 거의 비슷하다. 다른 건 다음 정점을 무엇을 기준으로 고르느냐, 딱 그 한 줄이다.

	Prim	Dijkstra
목적	최소 신장 트리(MST)	시작점에서의 최단 경로
시작점	정해지지 않음 (아무 데서나)	시작점 $v_0$이 정해져 있음
선택 기준	트리에 닿는 가장 가벼운 간선 $w(u,v)$	시작점에서 거리가 가장 짧은 정점 $d_{min}(v)$
갱신값	$\min\big(\text{key}(v),\ w(u,v)\big)$	$\min\big(d_{min}(v),\ d_{min}(u) + w(u,v)\big)$

결국 차이는 갱신값에 $d_{min}(u)$가 더해지느냐 아니냐로 좁혀진다. Prim은 트리에서 $v$로 가는 간선 하나의 무게만 보고, 다익스트라는 시작점에서 $v$까지 쌓인 거리를 본다. 보는 게 다르니 만들어지는 트리도 달라질 수 있다.

위 삼각형에서는 $C$를 어떻게 잇느냐에서 둘이 갈린다. Prim은 간선 무게만 보니까 $B{-}C(2)$로 $C$를 싸게 붙인다. 반면 다익스트라는 시작점 $A$로부터의 거리를 보는데, $A{-}C$를 직접 가면 3이고 $A \to B \to C$로 돌아가면 2+2=4라서, 더 짧은 직접 간선을 택한다. 같은 그래프를 놓고도 서로 다른 트리가 나오는 것이다.