다익스트라 알고리즘은 출발 노드에서 다른 모든 노드까지의 최단 거리를 구합니다. 아직 확정하지 않은 노드 중 거리가 가장 짧은 노드를 확정하고, 그 노드를 거쳐 가면 더 가까워지는 이웃의 거리를 고칩니다. 이 두 동작을 모든 노드가 확정될 때까지 반복합니다.

가중치 그래프에서 다익스트라 알고리즘이 거리를 확정하고 갱신하는 과정을 보여 주는 시뮬레이터

1. 그래프에서 출발 노드를 누르세요 (지금은 A)

2. 한 단계씩 진행하세요

미확정이번에 확정확정됨이번에 거리 확인한 간선확정된 최단 경로누른 노드까지의 경로

표에서 노란색 칸은 이번 단계에서 거리가 줄어든 노드입니다. 모든 단계가 끝난 뒤 그래프의 노드를 누르면 출발 노드에서 그 노드까지의 최단 경로가 표시됩니다.

왜 가장 가까운 노드부터 확정해도 될까요

미확정 노드 중 거리가 가장 짧은 노드를 u라고 하겠습니다. u로 가는 더 짧은 길이 있다면 그 길은 다른 미확정 노드를 거쳐야 하는데, 그 노드까지의 거리부터 이미 u보다 깁니다. 간선 가중치가 음수가 아니라면 거기서 더 가도 거리가 줄지 않으므로, u의 거리는 더 짧아질 수 없습니다. 그래서 다익스트라는 가중치가 음수인 간선이 있는 그래프에서는 쓸 수 없고, 그때는 벨만-포드 알고리즘을 씁니다.

실행 시간

매번 가장 가까운 노드를 찾는 데 우선순위 큐(힙)를 쓰면 O((V + E) log V) 시간이 걸립니다. 지도 앱의 길 찾기, 네트워크 라우팅 프로토콜 OSPF가 이 알고리즘을 바탕으로 합니다.