그림을 봅시다.

▲ 그림 14-2 relaxation 1

그림 14-2에서 이미 최단 경로가 밝혀진 집합 S는 {0, 2}입니다. distance[1]은 오직 S에 있는 정점만 거쳐서 정점 1에 도달하는 거리입니다. 현재 값은 30입니다. distance[4]는 오직 S에 있는 정점만 거쳐서 정점 4에 도달하는 거리입니다. 현재 값은 12이지요. 이때 정점 4를 S에 포함시킨다고 합시다. S=S U {4} 연산을 합니다.

다음 그림을 보면 정점 4가 S에 삽입되었습니다.

▲ 그림 14-3 relaxation 2