584
Graph Algorithms
In Figure 7.9, circled nodes are those in set IN, heavy lines show the current
shortest paths, and the d value for each node is written along with the node label.
Figure 7.9a is the picture after initialization.
(3)
1
(4)
3
(3)
1
(4)
3
4
1 (3)
3
x
8
3
1
1
y (10)
(a)
10
6
3 (4)
2 (8)
7
4 (∞)
4
(3)
3
x
8
3
1
1
y (10)
(b)
10
6
3 (4)
2 (8)
7
4 (∞)
4
3
x
1
(3)
1
(4)
3
8
3
1
y (6)
(d)
10
1
1
6
2 (8)
7
(5)
4 (5)
4
3
x
y
8
3
1
(6)
(e)
10
6
2 (8)
7
4
3
x
8
3
1
1
y (7)
(c)
10
6
2 (8)
7
4 (5)
4
Figure 7.9
We now enter the while loop and search through the d values for the node of
minimum distance that is not in IN; this turns out to be node 1, with d 314 = 3. We
throw node 1 into IN, and in the for loop we recompute all the d values for the
remaining nodes, 2, 3, 4, and y.
p = 1
IN = 5x, 16
d 32 4 = min(8, 3 + a31, 24) = min(8, ∞) = 8
d 33 4 = min(4, 3 + a31, 34) = min(4, 9) = 4
d 34 4 = min(∞, 3 + a31, 44) = min(∞, ∞) = ∞
d 3 y 4 = min(10, 3 + a31, y 4) = min(10, ∞) = 10
There were no changes in the d values, so there were no changes in the s values
(there were no shorter paths from x by going through node 1 than by going directly
from x). Figure 7.9b shows that 1 is now in IN.
The second pass through the while loop produces the following:
p = 3 (3 has the smallest d value, namely 4, of 2, 3, 4, or y)
IN = 5x, 1, 36