그러고 나서 그림 14-9에서 adj[2]를 구한 후 relaxation을 합니다.

▲ 그림 14-9 데이크스트라 6

즉, adj[2]={1, 3}에 대해 relaxation하고 있습니다. 최소 우선순위 큐에서 다음 원소를 pop하면 D[1]=8이므로 정점 1이 나오겠지요.

그림 14-10을 보면 최소 우선순위 큐에서 pop을 하면 거리가 가장 짧은 정점 1이 나옵니다.

▲ 그림 14-10 데이크스트라 7