최단거리 테이블은 각 노드에 대해 주어지며, 각 값들은 1번 노드에서 x번 노드로 가는 최단 경로를 의미한다.처음에는 1번노드에서 자기 자신의 거리는 0이고, 나머지는 무한(
INF)값으로 초기화한다.- Step 1 : 출발인 1번 노드를 선택하고, 해당 노드를 거쳐 갈 수 있는 다른 노드들(2번과 3번)의 거리를 계산하여 갱신한다. 무한값 보다 작으므로 갱신된다.
노드 위의 식별값은
[최단거리, 이전 노드](*) 로 표현되며, 방문한 적이 있는 노드는 더 이상 갱신할 필요가 없어 * 표시를 한다.1. Step 2: : 방문하지 않은 노드 중 가장 짧은 최단거리 노드(3번)를 선택하고 해당 노드를 거쳐갈 수 있는 다른 노드를 갱신한다.
- Step 3: : 마찬가지로 반복
여기서 중요한 점은 2번 노드에 의해 4번 노드의 최단거리가 13이었는데, 이번 단계에서 3번 노드에 의해 12로 갱신된다.
- 이 과정을 계속 반복하면 결국 아래와 같은 결과와 최단거리 테이블을 얻을 수 있다.
결국 1번 노드에서 다른 모든 노드로 가는 경로와 최단거리를 알 수 있다.
예를 들어, 1번 노드에서 8번노드로 가는 최단거리는 14이며, 경로는 8번 노드의 부모노드(4번)를 타고 쭉 트래킹하면
8<-4<-3<-1를 얻을 수 있다.