간선마다 가중치가 있는 그래프에서, 한 출발점으로부터 나머지 모든 정점까지의 최단 거리를 구하는 알고리즘이다. 가중치가 모두 같다면 BFS 로 충분하지만, 간선마다 비용이 다르면 “먼저 도달한 경로” 와 “가장 싼 경로” 가 달라지므로 별도의 방법이 필요하다.
동작
각 정점에 대해 “지금까지 알아낸 출발점으로부터의 최단 거리” 를 들고 있다가, 아직 확정되지 않은 정점 중 그 값이 가장 작은 것을 하나 확정한다.
- 출발점 거리를 0, 나머지를 무한대로 둔다
- 미확정 정점 중 거리가 가장 작은 정점 를 꺼내 확정한다
- 의 이웃 에 대해
dist[u] + w(u,v)가dist[v]보다 작으면 갱신한다 (relaxation) - 모든 정점이 확정될 때까지 2–3 을 반복한다
2번에서 “가장 작은 것” 을 매번 꺼내야 하므로 Heap 을 우선순위 큐로 쓴다. 그러면 정점 개, 간선 개에 대해 다.
왜 greedy 가 통하나
거리가 가장 작은 미확정 정점을 확정해도 되는 이유는, 그 값보다 더 싸게 도달할 경로가 남아 있을 수 없기 때문이다. 다른 경로로 돌아가려면 지금 확정하는 값보다 큰 거리를 이미 지나야 하는데, 간선 가중치가 음수가 아니므로 거리는 줄어들지 않는다.
이 논증이 음수 가중치에서는 깨진다. 나중에 음수 간선을 타면 확정한 거리보다 싸질 수 있어서, 음수 간선이 있으면 Bellman-Ford 를 쓴다.
같은 greedy algorithm 계열인 Prim algorithm 과 뼈대가 거의 같지만, 비교하는 값이 다르다. Dijkstra 는 출발점으로부터의 누적 거리를, Prim 은 트리에 붙이는 간선 하나의 가중치를 본다.