가중치가 있는 그래프에서 한 시작점으로부터 다른 모든 정점까지의 최단거리를 구한다. 가중치가 전부 같다면 BFS만으로도 최단거리가 나오지만, 간선마다 비용이 다르면 홉 수가 적은 경로와 비용이 싼 경로가 어긋나기 시작한다. 그 어긋나는 예는 BFS에 적어두었다.
거리 갱신과 확정 순서
거리 배열을 전부 무한대로 두고 시작점만 0으로 둔다. 그 다음 아직 확정되지 않은 정점 중 거리가 가장 작은 것을 꺼내는데, 이 순간 그 정점까지의 거리는 확정이다. 꺼낸 정점의 이웃들을 보면서 꺼낸 정점의 거리 + 간선 비용이 그 이웃에 적힌 거리보다 작으면 갱신한다. 꺼낼 것이 없을 때까지 반복한다.
while Q is not empty
set u = vertex in Q with min dist
Q.remove(u)
for each neighbor v of u
set alt = dist[u] + length(u, v)
if alt < dist[v]
set dist[v] = alt
두 번째 단계가 알고리즘 전체를 떠받친다. 한 번 꺼낸 정점은 다시 건드리지 않는다. 가장 작은 것부터 꺼냈으니 더 짧은 경로가 나중에 나올 수 없기 때문이다.
우선순위 큐와 복잡도
매번 최솟값을 찾아야 하니 우선순위 큐(최소 힙)를 쓴다. 간선을 한 번씩 보는데 거리가 갱신될 때마다 큐 안의 순서가 바뀔 수 있어서 간선 수에 큐 연산을 곱한 O(E log V)가 된다. 우선순위 큐 없이 단순 for문으로 전체를 스캔하면 O(V²)라, 간선이 조밀해 E가 V²에 가까우면 오히려 for문 쪽이 나을 수도 있다.
가까운 알고리즘들과 갈리는 기준
가중치가 전부 같으면 BFS로 충분하다. 모든 쌍의 최단거리가 필요하거나 음수 간선이 있으면 플로이드-워셜인데, 둘을 가르는 기준은 그쪽에 정리해두었다. 최소 신장 트리가 목적이면 프림 알고리즘이고, 갱신 기준 한 줄만 다른 거의 같은 알고리즘이다. 그 한 줄의 차이는 최소 신장 트리에 있다.
음수 간선
음수 간선에는 쓸 수 없다. 지금 꺼낸 게 가장 작으니 확정이라는 전제가 앞으로 더할 값이 전부 0 이상일 때만 성립하기 때문이다. 음수 간선이 있으면 이미 확정한 정점이 나중에 더 싸게 도달될 수 있고, 그러면 확정한 값이 틀린 답이 된다.
음수 간선이 있으면 벨만-포드나 플로이드-워셜을 쓴다.