그림 14-4에서 배열 D는 distance를 의미합니다. 배열 P는 predecessor로 최단 경로에서 바로 전에 지나온 정점을 의미합니다. 집합 S는 최단 경로를 밝힌 정점 집합입니다. 아직은 공집합입니다. 그림 14-4와 같이 D의 모든 정점을 무한대로, P의 모든 정점을 None으로 초기화합니다. 이번 예제에서는 시작 정점을 0으로 했습니다. 시작 정점 0에서 목적지 0까지 걸리는 거리는 얼마일까요? 당연히 0일 것입니다. 그러므로 D[0]은 0이 됩니다. 최소 우선순위 큐를 만든 후 (거리, 정점)의 쌍을 요소로 push합니다. 키는 거리입니다.

그럼 거리가 가장 짧은 요소가 다음에 pop되겠지요. 정점 0에서 쌍 (0, 0)을 만든 후 우선순위 큐에 push하겠습니다. 거리가 0인 정점 0을 알게 되었으니 이제 S에 0을 삽입하면 되겠지요. 다음 그림에서 이 과정을 진행합니다.

▲ 그림 14-5 데이크스트라 2