거리 후보를 시작한다
출발점의 거리를 0으로 두고 다른 정점은 아직 경로를 모르는 상태로 둔다. 다음으로 확정할 정점은 지금까지 알려진 출발점부터의 거리 후보가 가장 작은 정점이다. 간선 하나의 무게만 비교하는 것이 아니다.
간선을 완화한다
출발점에서 A까지의 거리 후보가 4이고 A→B의 가중치가 3이면 B까지 7의 경로를 얻는다. 기존 B의 후보가 10이었다면 7로 줄인다. 기존 후보가 6이라면 바꾸지 않는다.
음수 가중치의 문제
음수 간선이 있으면 나중에 더 먼 정점을 경유해 이미 확정한 거리를 줄일 수 있어 기본 논증이 성립하지 않는다. 그런 그래프에 표준 다익스트라 알고리즘을 그대로 적용해서는 안 된다. 0인 가중치는 음수와 달리 허용된다.
구현과 결과
우선순위 큐로 작은 거리 후보를 빠르게 선택할 수 있다. 실제 경로를 복원하려면 거리가 개선될 때 이전 정점이나 간선도 기록한다. 출발점에서 도달할 수 없는 정점은 유한한 최단 거리를 얻지 못한다.
관련 문서
최단 경로 / 가중 그래프 / 유향 그래프 / 우선순위 큐 / 프림 알고리즘 / 간선 (그래프 이론) / 정점 (그래프 이론)