Dijkstra
다익스트라
가중치가 있는 그래프에서, 한 정점에서 모든 정점까지의 최단 거리를 구한다.
BFS는 모든 간선의 비용을 1로 볼 때만 맞다.
(1) (2)
A ----- B ----- C
\ /
\___________/
(10) A→C 직항은 10인데,
B를 거쳐 가면 1 + 2 = 3 이다
BFS는 한 칸으로 갈 수 있는 직항을 먼저 찾고 끝내버린다. 칸 수만 보니까. 하지만 실제 최단은 두 칸짜리 경로다.
다익스트라는 칸 수 대신 누적 비용이 작은 순서로 방문한다.
왜 이게 최단 거리를 보장하나
핵심 전제는 하나다. 간선 가중치가 음수가 아니다. 왜 그 전제로 최단이 보장되는지는 도화선으로 생각하면 쉽다.
정점은 화약이 놓인 지점, 간선은 정점끼리 이어놓은 도화선이다. 가중치는 도화선 길이, 즉 타는 데 걸리는 시간이다.
시작 지점에 불을 붙인다. 불은 도화선을 따라 모든 방향으로 동시에 번진다. 화약에 불이 닿으면 그 지점이 터지고, 거기 매달린 도화선 전부에 옮겨붙는다.
어떤 지점이 터진 시각 = 그 지점까지의 최단 거리다.
왜 터진 시각이 최단인가
터지는 순간을 붙잡고 물어보자. 더 일찍 터질 방법이 있었나?
없다. 불은 놓친 길이 없다. 갈 수 있는 모든 도화선에서 처음부터 동시에 타들어 가고 있었으니까. 더 짧은 경로가 있었다면 그쪽 불이 먼저 도착했을 테고, 그럼 이미 그때 터졌을 것이다. 지금 터졌다는 사실 자체가 이보다 빠른 길은 없었다는 증거다.
그래서 터진 지점은 두 번 볼 필요가 없다.
예정과 실제는 다르다
불이 아직 도화선 중간을 타는 동안, 그 끝의 지점은 "몇 시에 터질 예정" 상태다. 예정이라 얼마든지 바뀐다. 더 짧은 도화선을 타고 온 불이 먼저 닿을 참이면 앞당겨진다.
하지만 실제로 터진 시각은 안 바뀐다. 터진 걸 되돌릴 순 없으니까.
dist[v]는 v가 pop되기 전까지는 예정표고, pop되는 순간 실제 터진 시각으로 굳는다.
구현
앞 글의 Heap을 그대로 쓴다.
function dijkstra(graph, start, n) {
// 각 지점의 도착 예정 시각표. 불이 닿을 기미가 없으면 무한대
const dist = new Array(n + 1).fill(Infinity);
// 여기에 불을 붙인다. 시각 0
dist[start] = 0;
// 지금 타고 있는 도화선들. 가장 이른 도착부터 꺼내야 하므로 최소 힙
const pq = new Heap((a, b) => a[1] - b[1]);
pq.push([start, 0]);
while (pq.size() > 0) {
// node : 다음으로 터질 지점
// cost : 이 항목이 등록될 때 계산된 도착 예정 시각
const [node, cost] = pq.pop();
// 이미 터진 자리에 늦게 도착한 불 → 아무 일도 안 일어난다
if (cost > dist[node]) continue;
// node가 터졌다. 여기 매달린 도화선들에 불이 옮겨붙는다
for (const [next, weight] of graph[node]) {
// 이 도화선을 다 태우면 next에 닿는 시각
const nextCost = cost + weight;
// 기존 예정보다 이르면 그게 새 예정이 된다
if (nextCost < dist[next]) {
dist[next] = nextCost;
pq.push([next, nextCost]);
}
}
}
// 각 지점이 터진 시각 = 최단 거리
return dist;
}
동작 따라가기
1번에서 출발한다. 그래프는 이렇게 생겼다.
2 1 3
(1) ────────→ (2) ────────→ (3) ────────→ (4)
│ ↑
└───────────────────────────┘
5
1에서 3으로 가는 길이 두 개다. 직행 5와 2를 거쳐 2+1=3. 직행이 먼저 발견되지만 그게 최단이 아니다. 여기가 이 예제의 핵심이다.
노드: 1 2 3 4
dist = [ _, 0, ∞, ∞, ∞ ] 힙: [1,0]
(1) pop [1,0] → 1의 이웃 2와 3을 본다
2: 0+2=2 (∞보다 싸다) 갱신
3: 0+5=5 (∞보다 싸다) 갱신
dist = [ _, 0, 2, 5, ∞ ] 힙: [2,2] [3,5]
(2) pop [2,2] → 2의 이웃 3을 본다
3: 2+1=3 (5보다 싸다) 갱신 ← 최단이 바뀌는 순간
dist = [ _, 0, 2, 3, ∞ ] 힙: [3,3] [3,5]
↑ ↑
새 정보 철 지난 정보가 같이 있다
(3) pop [3,3] → 3의 이웃 4를 본다
4: 3+3=6 (∞보다 싸다) 갱신
dist = [ _, 0, 2, 3, 6 ] 힙: [3,5] [4,6]
(4) pop [3,5] → 5 > dist[3]=3 → continue (철 지난 정보, 이웃 안 봄)
(5) pop [4,6] → 4에서 나가는 간선 없음
힙이 비었다 → 종료
최종 dist = [ _, 0, 2, 3, 6 ]
(2)에서 3번 노드가 5 → 3으로 줄었다. 먼저 발견한 경로가 최단 경로가 아니었던 케이스다.
시간 복잡도
V는 정점 개수, E는 간선 개수
시간복잡도는 연산 횟수 × 연산 하나의 비용
- 연산 횟수 —
push는 간선을 훑을 때만 일어나고 간선 하나당 많아야 한 번이다 → 최대E번 - 연산 하나 — 힙은 완전 이진 트리라
log(heap.length)만큼 오르내린다. 그런데 push가 최대E번이니heap.length도E를 넘지 못한다 →log(heap.length) ≤ log E - 곱하면
E log E - 간선은 정점 쌍을 고르는 것이므로
E ≤ V²→log E ≤ log V² = 2 log V, 상수는 떼고log V
정리하면 O(E log V).