ReminDeR
Distances in Dijkstra’s
algorithm are always
recomputed relative to the
node most recently added
to IN.
d324 = min(8, 4 + a33, 24) = min(8, 4 + ∞) = 8
d 34 4 = min(∞, 4 + a33, 44) = min(∞, 4 + 1) = 5 (a change, so update s 34 4 to 3)
d3 y 4 = min(10, 4 + a33, y 4) = min(10, 4 + 3) = 7 (a change, so update s 3 y 4 to 3)
x
1
2
3
4
y
d
0
3
8
4
5
7
s
−
x
x
x
3
3
x
1
2
3
4
y
d
0
3
8
4
5
6
s
−
x
x
x
3
4
x
1
2
3
4
y
d
0
3
8
4
5
6
s
−
x
x
x
3
4
Shorter paths from x to the two nodes 4 and y were found by going through 3, as
reflected in Figure 7.9c.
On the next pass,
p = 4 (d value = 5)
IN = 5x, 1, 3, 46
d 32 4 = min(8, 5 + 7) = 8
d 3 y 4 = min(7, 5 + 1) = 6
(a change, update s 3 y 4)
See Figure 7.9d.
Processing the while loop again, we get
p = y
IN = 5x, 1, 3, 4, y6
d 32 4 = min(8, 6 + ∞) = 8
See Figure 7.9e.
Now that y is part of IN, the while loop terminates. The path goes through
y, s 3 y 4 = 4, s 34 4 = 3, and s 33 4 = x. Thus the path uses nodes x, 3, 4, and y. (The
algorithm gives us these nodes in reverse order.) The distance for the path is
d3 y 4 = 6. By looking at the graph in Figure 7.7 and checking all the possibilities,
we can see that this is the shortest path from x to y.
Dijkstra’s algorithm terminates when y is put into IN, even though there may
be other nodes in the graph not yet in IN (such as node 2 in Example 8). How do
we know that a still shorter path cannot be found through one of these excluded
nodes? If we continue processing until all nodes have been included in IN, the
d values then represent the shortest path from x to any node, using all the values
in IN, that is, the shortest path using any nodes of the graph. But new nodes are
brought into IN in order of increasing d values. A node z that is brought into IN
later than y must have as its shortest path from x one whose distance is at least as
Section 7.3 Shortest Path and Minimal Spanning Tree
585
Distances in Dijkstra’s
algorithm are always
recomputed relative to the
node most recently added
to IN.
d324 = min(8, 4 + a33, 24) = min(8, 4 + ∞) = 8
d 34 4 = min(∞, 4 + a33, 44) = min(∞, 4 + 1) = 5 (a change, so update s 34 4 to 3)
d3 y 4 = min(10, 4 + a33, y 4) = min(10, 4 + 3) = 7 (a change, so update s 3 y 4 to 3)
x
1
2
3
4
y
d
0
3
8
4
5
7
s
−
x
x
x
3
3
x
1
2
3
4
y
d
0
3
8
4
5
6
s
−
x
x
x
3
4
x
1
2
3
4
y
d
0
3
8
4
5
6
s
−
x
x
x
3
4
Shorter paths from x to the two nodes 4 and y were found by going through 3, as
reflected in Figure 7.9c.
On the next pass,
p = 4 (d value = 5)
IN = 5x, 1, 3, 46
d 32 4 = min(8, 5 + 7) = 8
d 3 y 4 = min(7, 5 + 1) = 6
(a change, update s 3 y 4)
See Figure 7.9d.
Processing the while loop again, we get
p = y
IN = 5x, 1, 3, 4, y6
d 32 4 = min(8, 6 + ∞) = 8
See Figure 7.9e.
Now that y is part of IN, the while loop terminates. The path goes through
y, s 3 y 4 = 4, s 34 4 = 3, and s 33 4 = x. Thus the path uses nodes x, 3, 4, and y. (The
algorithm gives us these nodes in reverse order.) The distance for the path is
d3 y 4 = 6. By looking at the graph in Figure 7.7 and checking all the possibilities,
we can see that this is the shortest path from x to y.
Dijkstra’s algorithm terminates when y is put into IN, even though there may
be other nodes in the graph not yet in IN (such as node 2 in Example 8). How do
we know that a still shorter path cannot be found through one of these excluded
nodes? If we continue processing until all nodes have been included in IN, the
d values then represent the shortest path from x to any node, using all the values
in IN, that is, the shortest path using any nodes of the graph. But new nodes are
brought into IN in order of increasing d values. A node z that is brought into IN
later than y must have as its shortest path from x one whose distance is at least as
Section 7.3 Shortest Path and Minimal Spanning Tree
585