시작 정점의 거리를 0으로, 이외 정점들은 무한대로 초기화한다.
정점 1의 인접 정점 거리를 업데이트한 뒤 정점 1은 방문 표시한다.
-
d[2] = min(d[1]+정점 1에서 정점 2까지의 거리, inf) = min(0+2, inf) = 2
-
d[4] = min(d[1]+정점 1에서 정점 4까지의 거리, inf) = min(0+1, inf) = 1
(d[1]: 시작 정점에서 정점 1까지의 최단 거리)
방문하지 않은 정점들 중 **거리가 가장 작은 정점(4)**을 택한 뒤, [단계 2]와 동일하게 인접 정점의 거리를 업데이트하고 정점 4는 방문 표시한다.
- d[2] = min(d[4]+정점 4에서 정점 2까지의 거리, inf) = min(1+2, 2) = 2
- d[5] = min(d[4]+정점 4에서 정점 5까지의 거리, inf) = min(1+1, inf) = 2
[단계 3]을 반복한다.
- 방문하지 않은 정점들 중 거리가 가장 작은 정점은 2이다.
- d[4] = min(d[2]+정점 2에서 정점 4까지의 거리, 1) = min(2+2, 1) = 1
- d[3] = min(d[2]+정점 2에서 정점 3까지의 거리, inf) = min(2+3, inf) = 5
