Graphics Reference
In-Depth Information
Table 9.2.
Stages of Dijkstra's algorithm on the network of Figure 9.7 including
the backward pointers. Shortest path costs to known nodes are shown in bold. The
shortest path to Z is the path ABDEGZ of cost 8.
A B C D E F G Z
0
∞ ∞ ∞ ∞ ∞ ∞ ∞
∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅
A B C D E F G Z
0
1 3
∞ ∞ ∞ ∞ ∞
∅
A A
∅ ∅ ∅ ∅ ∅
A B C D E F G Z
0 1
2 4
∞ ∞ ∞ ∞
∅
∅ ∅ ∅ ∅
A B B
A B C D E F G Z
0 1 2
4 7 6
∞ ∞
∅
A B B C C
∅ ∅
A B C D E F G Z
0 1 2 4
5 6
∞
11
∅
A B B D C
∅
D
A B C D E F G Z
0 1 2 4 5
6 6 11
∅
A B B D C E D
A B C D E F G Z
0 1 2 4 5 6
6 11
∅
A B B D C E D
A B C D E F G Z
0 1 2 4 5 6 6
8
∅
A B B D C E G
A B C D E F G Z
0 1 2 4 5 6 6 8
∅
A B B D C E G
Search WWH ::
Custom Search