간선 가중치가 음수가 아니라면, 우선순위 큐에서 가장 작은 거리로 꺼낸 노드의 거리는 그 순간 확정된다. 이 한 문장이 정렬·BFS·동적계획을 하나로 묶는 그리디 최단경로의 핵심이다. 이 페이지는 그 정당성을 증명하고, Expert 문제들이 이 원리를 어떻게 변형해 쓰는지 추적한다.
가중 그래프 G = (V, E, w)와 출발 노드 s가 주어졌을 때, s에서 다른 모든 노드까지의 최소 비용 경로를 구한다. 단, 모든 간선 가중치 w(e) ≥ 0이다.
다익스트라의 발상은 단순하다. "아직 거리가 확정되지 않은 노드 중, 현재까지 알려진 잠정 거리가 가장 작은 노드는 — 그 잠정 거리가 곧 진짜 최단거리다." 이 노드를 확정하고, 그 이웃들의 잠정 거리를 갱신(완화, relax)한다. 모든 노드가 확정될 때까지 반복한다.
왜 "가장 작은 잠정 거리"를 믿어도 되는가? 그 답이 §2의 정리다.
모든 간선 가중치가 비음일 때, 우선순위 큐에서 노드 u를 처음 꺼내는 순간의 dist[u]는 s에서 u까지의 진짜 최단거리와 같다.
꺼낸 시점의 dist[u]가 진짜 최단거리 δ(u)보다 크다고 하자(작을 수는 없다 — dist는 항상 실제 경로 비용이므로). u는 그런 노드 중 가장 먼저 잘못 꺼내진 노드라고 두자.
진짜 최단경로 P: s → … → u를 따라가면, S(이미 확정된 집합) 안에 있는 노드에서 S 밖으로 처음 나가는 간선 (x, y)이 존재한다. x ∈ S이므로 x는 올바르게 확정됐고(가정상 u가 첫 오류), x가 확정될 때 간선 (x, y)가 relax되어 dist[y] ≤ δ(x) + w(x,y) = δ(y)가 된다.
경로 P에서 y 이후 구간의 비용은 비음이므로 δ(y) ≤ δ(u). 종합하면 dist[y] ≤ δ(y) ≤ δ(u) < dist[u]. 그런데 u를 y보다 먼저 꺼냈다면 dist[u] ≤ dist[y]여야 하므로 모순.
우선순위 큐로 이진 힙을 쓰면 O((V + E) log V)다. 거리 감소 시 힙 내부를 갱신하는 대신 새 항목을 그냥 push하고, pop 후 "이미 확정된 노드면 버리는" 게으른 삭제(lazy deletion)가 구현이 가장 단순하다.
#include <vector>#include <queue>using namespace std;struct Edge { int to; long long w; };// adj: 인접 리스트, s: 출발 노드 → dist[] 채움void dijkstra(int s, vector<vector<Edge>>& adj, vector<long long>& dist) { const long long INF = 4e18; dist.assign(adj.size(), INF); dist[s] = 0; // (거리, 노드) — 최소 힙. 거리를 앞에 두어 거리순 정렬 priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; // 게으른 삭제: 낡은 항목 for (auto& e : adj[u]) { if (dist[u] + e.w < dist[e.to]) { // relax dist[e.to] = dist[u] + e.w; pq.push({dist[e.to], e.to}); } } }}
d > dist[u] 검사가 게으른 삭제의 핵심이다. 같은 노드가 거리 갱신마다 힙에 여러 번 들어가지만, 가장 작은 거리의 항목이 먼저 pop되어 노드를 확정하고, 이후 꺼내지는 낡은 항목들은 이 검사로 폐기된다. 힙 크기는 O(E)까지 커질 수 있으나 시간 복잡도의 log 항은 log E = O(log V)로 흡수된다.
각 간선은 최대 한 번 relax되어 push를 일으키므로 힙 연산은 O(E)회, 각 연산이 O(log V). 정점 추출도 O(V log V). 합쳐 O((V + E) log V). 공간은 힙 O(E) + 거리 배열 O(V). 밀집 그래프에서 인접 행렬 + 선형 argmin 버전은 O(V²)이며, E ≈ V²일 때 오히려 더 빠르다.
Expert 문제에서 다익스트라는 교과서 형태 그대로 등장하는 일이 드물다. 거의 항상 상태 공간을 확장하거나 비용 모델을 문제에 맞춰 재정의한다.
로봇청소기의 다익스트라는 노드가 칸 (r, c)가 아니라 칸과 방향의 쌍 (r, c, dir)이다. 회전(TURN)에 비용이 붙기 때문이다. 같은 칸이라도 어느 방향으로 도착했는지에 따라 다음 회전 비용이 달라지므로, 방향을 상태에 넣지 않으면 비용 모델이 틀린다. 노드 수는 4배가 되지만 — 4는 상수이므로 복잡도 차수는 그대로다.
노후화된도로에서 한 도로를 통과하는 비용은 "도로 상태가 화물 무게보다 낮으면 보수(repair)가 필요"라는 규칙에서 합성된다. cost(e) = 10 + max(0, W − status)·W 같은 식을 간선 가중치로 환산하면, 그 다음은 표준 비음 가중 최단경로다. 핵심은 "문제의 비용 규칙을 비음 간선 가중치로 번역할 수 있는가"이며, 번역만 되면 §2의 정리가 그대로 보장을 준다.
대피소는 노드가 3개뿐인 초소형 그래프에서 다익스트라를 반복 호출해 최소비용 흐름(transshipment)을 흉내 낸다. 그래프가 작으면 매 반복의 우선순위 큐가 실시간으로 갱신되어, 큰 그래프에서 Max-Flow를 쓰는 것보다 구현이 단순하고 실전 정확도도 높다.
| 알고리즘 | 시간 | 음의 간선 | 쓰임 |
|---|---|---|---|
| BFS | O(V+E) | — | 모든 간선 가중치가 1인 특수 케이스 |
| 0-1 BFS | O(V+E) | — | 가중치가 0 또는 1 — 덱(deque)으로 |
| Dijkstra | O((V+E)log V) | 불가 | 비음 가중 단일 출발 — 가장 흔한 선택 |
| Bellman-Ford | O(VE) | 가능 | 음의 간선 — 음의 사이클 검출도 |
| Floyd-Warshall | O(V³) | 가능 | 전쌍(all-pairs) — V가 작을 때(쓰레기통) |
BFS는 다익스트라의 특수 케이스다 — 모든 간선이 같은 가중치면 큐가 곧 우선순위 큐 역할을 한다. 거꾸로 다익스트라는 "가중치 BFS"라고 봐도 좋다. 전쌍 거리가 필요하고 정점 수가 수백 이하라면 Floyd-Warshall의 O(V³)이 다익스트라 V회 호출보다 코드가 짧고 캐시 친화적이다.