다익스트라 알고리즘
개요
다익스트라 알고리즘(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 공개 시연을 준비하며 네덜란드 64개 도시 철도망의 최단 경로 문제를 고안했다고 밝혔다. 로테르담에서 흐로닝언까지 가는 최단 경로 알고리즘 자체는 아침 커피를 마시던 약 20분 만에 종이와 연필 없이 구상됐다.2 원래 1959년 논문 방식은 정점 선택에 시간이 걸렸으나, 1977년 Donald B. Johnson이 -원 힙(d-ary heap)을 적용했고 1984년 Michael L. Fredman과 Robert E. Tarjan이 피보나치 힙을 도입해 점근 복잡도를 까지 낮췄다.3
임시 거리 확정과 간선 완화
출발점 의 초기 거리는 으로 두고, 아직 경로를 모르는 나머지 정점은 로 채운다. 매 단계마다 아직 확정되지 않은 정점 집합 에서 임시 거리가 가장 작은 정점 를 골라 확정 집합 에 넣는다. 모든 간선의 가중치가 비음수()이므로, 아직 확정되지 않은 다른 정점을 거쳐 로 돌아오는 어떤 우회 경로도 보다 짧아질 수 없다.
정점 의 최단 거리가 확정되면 에서 나가는 간선 를 하나씩 확인해 기존 임시 거리 보다 가 작을 때 값을 갱신한다. 이 단계를 간선 완화(relaxation)라 부른다. 아래 그림에서는 직행 비용 를 먼저 기록했다가, 비용 인 를 먼저 확정한 뒤 경로(비용 )로 완화한다.
실행 예제
작은 방향 그래프에서 정점 선택 과정을 한눈에 볼 수 있도록, 별도 힙 자료구조 없이 거리 배열 전체를 훑어 최소 후보를 고르는 방식으로 작성했다. 정점 번호와 출발점은 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이면 루프를 즉시 종료해 도달 불가능한 정점에서 불필요한 완화 시도를 하지 않는다.
C++ 예제
C++에서는 std::priority_queue에 std::greater<>를 넘겨 최소 힙을 구성하고, 위에서 설명한 지연 삽입(lazy insertion)과 if (d > distance[from]) continue; 가드로 다익스트라를 구현한다.
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
struct Edge {
int to;
std::int64_t weight;
};
constexpr std::int64_t kInf = std::numeric_limits<std::int64_t>::max();
std::vector<std::int64_t> dijkstra(
const std::vector<std::vector<Edge>>& graph, int start) {
std::vector<std::int64_t> distance(graph.size(), kInf);
using Entry = std::pair<std::int64_t, int>;
std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> pq;
distance[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
auto [d, from] = pq.top();
pq.pop();
// 지연 삽입(lazy insertion)으로 남은 낡은 항목은 건너뛴다.
if (d > distance[from]) continue;
for (const Edge& edge : graph[from]) {
std::int64_t candidate = d + edge.weight;
if (candidate < distance[edge.to]) {
distance[edge.to] = candidate;
pq.push({candidate, edge.to});
}
}
}
return distance;
}
int main() {
// 정점 순서는 S(0), A(1), B(2), T(3), U(4)이며 U로 들어오는 간선은 없다.
const std::vector<std::vector<Edge>> graph{
{{1, 4}, {2, 1}}, {{3, 1}}, {{1, 2}, {3, 5}}, {}, {}};
const auto dist = dijkstra(graph, 0);
for (std::size_t i = 0; i < dist.size(); ++i) {
if (i > 0) std::cout << ',';
if (dist[i] == kInf) std::cout << "INF";
else std::cout << dist[i];
}
std::cout << '\n';
return 0;
}실행 결과:
0,3,1,4,INF비용과 실무 경계
배열 스캔 방식은 정점 선택 번에 , 모든 간선 완화에 가 걸려 총 시간과 보조 공간을 쓴다. 간선이 빽빽한 밀집 그래프()에서는 이 방식이 힙 오버헤드가 없어 빠르지만, 일반적인 희소 그래프에서는 이진 힙(우선순위 큐)을 써서 시간에 처리한다.
실무에서 우선순위 큐로 다익스트라를 구현할 때는 두 가지 함정을 조심해야 한다. 첫째, 표준 라이브러리의 우선순위 큐는 흔히 기존 원소의 우선순위를 낮추는 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. 저자 회고. ↩
- 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. ↩