Section 7.3 Shortest Path and Minimal Spanning Tree
583
example 8
Consider the graph in Figure 7.7 and the corresponding modified adjacency matrix
shown in Figure 7.8.
x
1
2
3
4
y
F
∞ 3 8 4 ∞ 10
3 ∞ ∞ 6 ∞ ∞
8 ∞ ∞ ∞ 7 ∞
4
6 ∞ ∞ 1
3
∞ ∞ 7 1 ∞
1
10 ∞ ∞ 3 1 ∞
V
Figure 7.7
Figure 7.8
Let’s trace Dijkstra’s algorithm on this graph. At the end of the initialization phase,
IN contains only x, d contains all the direct distances (arc weights) from x to other
nodes, and x is the immediate predecessor of all nodes except x. (Because of the
∞ in position a3x, 4 4, there is no arc from x to 4, so s 344 is meaningless here but
it simplifies the initialization.)
IN = 5x6
x
1
2
3
4
y
d
0
3
8
4
∞
10
s
−
x
x
x
x
x
//write out path nodes
write (“In reverse order, the path is”)
write (y)
z = y
repeat
write (s 3z 4)
z = s 3z 4
until z = x
// write out path distance
write (“The path distance is”, d 3 y 4 )
end Dijkstra
x 1
2 3
4 y