다익스트라 알고리즘
개요
다익스트라 알고리즘(Dijkstra’s algorithm)은 모든 간선의 가중치가 0 이상인 그래프에서 한 출발점으로부터 다른 모든 정점까지의 최단 거리를 구한다. 환승 횟수가 아니라 실제 이동 시간을 줄이려 할 때는 정거장 수가 적어도 구간 소요 시간이 긴 노선보다, 조금 돌아가더라도 누적 시간이 짧은 노선을 먼저 확장해야 한다.
연혁
Edsger W. Dijkstra는 1959년 3쪽 분량의 논문 「A Note on Two Problems in Connexion with Graphs」에서 최소 신장 트리와 두 정점 사이의 최단 경로를 함께 다뤘다. 오늘날 다익스트라 알고리즘이라 부르는 최단 경로 해법은 이 논문의 두 번째 문제에 해당한다.1
Dijkstra는 1983년에 공개된 회고에서 1956년 네덜란드 수학센터(Mathematisch Centrum)의 새 컴퓨터 ARMAC 시연을 위해 네덜란드 철도망의 최단 경로를 계산했다고 설명했다.2 2001년 구술을 정리해 2010년 발표한 인터뷰에서는 64개 도시를 고른 도로 지도와 로테르담–흐로닝언 경로, 커피를 마시며 약 20분 만에 종이와 연필 없이 해법을 구상한 장면을 회고했다.3 원래 1959년 논문 방식은 정점 선택에 시간이 걸렸으나, 1977년 Donald B. Johnson이 -원 힙(d-ary heap)을 적용했고 1984년 Michael L. Fredman과 Robert E. Tarjan이 피보나치 힙을 도입해 점근 복잡도를 까지 낮췄다.4
임시 거리 확정과 간선 완화
출발점 의 초기 거리는 으로 두고, 아직 경로를 모르는 나머지 정점은 로 채운다. 매 단계마다 아직 확정되지 않은 정점 집합 에서 임시 거리가 가장 작은 정점 를 골라 확정 집합 에 넣는다. 모든 간선의 가중치가 비음수()이므로, 아직 확정되지 않은 다른 정점을 거쳐 로 돌아오는 어떤 우회 경로도 보다 짧아질 수 없다.
정점 의 최단 거리가 확정되면 에서 나가는 간선 를 하나씩 확인해 기존 임시 거리 보다 가 작을 때 값을 갱신한다. 이 단계를 간선 완화(relaxation)라 부른다. 아래 그림에서는 직행 비용 를 먼저 기록했다가, 비용 인 를 먼저 확정한 뒤 경로(비용 )로 완화한다.
실행 예제
C++20
C++20판은 정수 비용을 long long에 담는다. 정점 번호와 출발점은 유효한 인덱스이고, 모든 가중치는 0 이상이며 계산하는 경로 합은 long long의 최댓값보다 작다고 전제한다. 그 최댓값 INF는 도달 불가 표시에만 쓰고, 출력에서는 TypeScript와 같이 Infinity로 표시한다.
#include <cstddef>
#include <iostream>
#include <limits>
#include <vector>
using Distance = long long;
struct Edge { std::size_t to; Distance weight; };
using Graph = std::vector<std::vector<Edge>>;
constexpr Distance INF = std::numeric_limits<Distance>::max();
std::vector<Distance> dijkstra(const Graph& graph, std::size_t start) {
const auto n = graph.size();
std::vector<Distance> distance(n, INF);
std::vector<bool> settled(n, false);
distance[start] = 0;
for (std::size_t step = 0; step < n; ++step) {
auto from = n;
for (std::size_t vertex = 0; vertex < n; ++vertex) {
if (!settled[vertex] && (from == n || distance[vertex] < distance[from])) {
from = vertex;
}
}
// 도달할 수 있는 미확정 정점이 더 없으면 종료한다.
if (from == n || distance[from] == INF) break;
settled[from] = true;
for (const auto& edge : graph[from]) {
if (settled[edge.to]) continue;
const auto candidate = distance[from] + edge.weight;
if (candidate < distance[edge.to]) distance[edge.to] = candidate;
}
}
return distance;
}
int main() {
// 정점 순서는 S, A, B, T, U이다.
const Graph graph{{{1, 4}, {2, 1}}, {{3, 1}}, {{1, 2}, {3, 5}}, {}, {}};
const auto distance = dijkstra(graph, 0);
for (std::size_t i = 0; i < distance.size(); ++i) {
if (i != 0) std::cout << ',';
if (distance[i] == INF) std::cout << "Infinity";
else std::cout << distance[i];
}
std::cout << '\n';
return 0;
}0,3,1,4,InfinityTypeScript
작은 방향 그래프에서 정점 선택 과정을 한눈에 볼 수 있도록, 별도 힙 자료구조 없이 거리 배열 전체를 훑어 최소 후보를 고르는 방식으로 작성했다. 정점 번호와 출발점은 0..graph.length-1 범위이고, 가중치는 0 이상의 안전한 정수이며 경로 합은 Number.MAX_SAFE_INTEGER 이내로 가정한다.
type Edge = Readonly<{ to: number; weight: number }>;
function dijkstra(graph: readonly (readonly Edge[])[], start: number): number[] {
const distance = new Array<number>(graph.length).fill(Infinity);
const settled = new Array<boolean>(graph.length).fill(false);
distance[start] = 0;
for (let step = 0; step < graph.length; step++) {
let from = -1;
for (let vertex = 0; vertex < graph.length; vertex++) {
if (!settled[vertex] && (from === -1 || distance[vertex]! < distance[from]!)) {
from = vertex;
}
}
// 남은 미확정 정점이 모두 도달 불가(Infinity)이면 탐색을 마친다.
if (from === -1 || distance[from] === Infinity) break;
settled[from] = true;
for (const edge of graph[from]!) {
if (settled[edge.to]) continue;
const candidate = distance[from]! + edge.weight;
if (candidate < distance[edge.to]!) distance[edge.to] = candidate;
}
}
return distance;
}
// 정점 순서는 S(0), A(1), B(2), T(3), U(4)이며 U로 들어오는 간선은 없다.
const graph: Edge[][] = [
[{ to: 1, weight: 4 }, { to: 2, weight: 1 }],
[{ to: 3, weight: 1 }],
[{ to: 1, weight: 2 }, { to: 3, weight: 5 }],
[], [],
];
console.log(dijkstra(graph, 0).join(','));0,3,1,4,Infinity출력은 순서대로 S, A, B, T, U의 최단 거리다. T까지는 경로로 비용 4가 들고, 들어오는 간선이 없는 고립 정점 U는 Infinity로 남는다. 남은 미확정 정점의 최소 거리가 Infinity이면 루프를 즉시 종료해 도달 불가능한 정점에서 불필요한 완화 시도를 하지 않는다.
비용과 실무 경계
배열 스캔 방식은 정점 선택 번에 , 모든 간선 완화에 가 걸려 총 시간과 보조 공간을 쓴다. 간선이 빽빽한 밀집 그래프()에서는 이 방식이 힙 오버헤드가 없어 빠르지만, 일반적인 희소 그래프에서는 정점당 항목 하나를 유지하고 decrease-key로 갱신하는 이진 힙을 써서 시간에 처리한다.
실무에서 우선순위 큐로 다익스트라를 구현할 때는 두 가지 함정을 조심해야 한다. 첫째, 표준 라이브러리의 우선순위 큐는 흔히 기존 원소의 우선순위를 낮추는 decrease-key 연산을 제공하지 않는다. 대신 거리 갱신 때마다 새 쌍 (candidate, v)를 큐에 중복 삽입(lazy insertion)하고, 큐에서 꺼낸 직후 if (d > distance[u]) continue; 가드로 낡은 항목을 버려야 한다. 이 중복 삽입 방식은 평행 간선까지 허용하는 그래프에서 큐가 최대 개 항목을 보관하며, 총시간은 이다. 이 한 줄이 빠지면 같은 정점의 인접 간선을 여러 번 다시 완화해 최악 시간 복잡도가 급격히 망가진다. 둘째, 음수 가중치 간선이 하나라도 있으면 "가장 작은 임시 거리는 더 이상 줄어들지 않는다"는 전제가 깨진다. 음수 간선이 있는 그래프에서는 벨만-포드(Bellman–Ford) 알고리즘을 써야 한다.
같이 보기
각주
- E. W. Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numerische Mathematik 1, 1959, pp.269–271, Problem 2. CWI 원문, DOI. ↩
- E. W. Dijkstra, “This Week’s Citation Classic,” Current Contents, 1983-02-14. 본문 작성일 1982-12-08. 저자 회고. ↩
- Thomas J. Misa (ed.), “An Interview with Edsger W. Dijkstra,” Communications of the ACM 53(8), 2010, pp.41–47, especially pp.42–43; oral interview recorded in 2001. Paper, DOI. ↩
- Michael L. Fredman, Robert Endre Tarjan, “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms,” 25th Annual Symposium on Foundations of Computer Science (FOCS), 1984, pp.338–346; JACM 34(3), 1987, pp.596–615, DOI. ↩