6.5 SHORTEST-PATH ALGORITHM 165Beginning our path at node A gives us four possible edges to consider. Of
those four, the edge AB is the shortest.
Node B is added to our shortest path tree (Fig. 6.8(c)), and we now look at
updating the paths. Nodes E and G can now be reached, so they are added. We
also look at node D and compare its direct path from node A of length 7 with
the path that goes through node B, which is of length 8. Because the direct
path is shorter, there is no change to the edge for node D. In looking at the
options, we see that the path from node A to node C is of length 4 and is the
shortest. The edge BE is shorter, but we are now considering the entire path
from node A and so the length of the path to node E is actually 5.
Node C is added to the shortest path tree (Fig. 6.8(d)). In examining the
graph, we see that we can get to node F through node C, but that total path
length is 10, which is longer than the current path to node F and so there are
no changes.
Given the situation in Fig. 6.8(d), we could choose either the path from
node A to node F or the path from node A to node E that goes through node
B, because they are both of length 5. The one chosen during a program execu-
tion will depend on the way the data is stored. For our purposes, when
presented with a choice, we will select the node that is alphabetically smaller to
get Fig. 6.8(e). Because the addition of node E to the graph didn’t change any
4 7 5 2 3 8BFEDCGA(^47)
5
(^23)
8
D
F
E
G
C
B
A
■FIGURE 6.8C
Path of length 4 to node
C is the shortest of the
options
■FIGURE 6.8D
The path of length 5 to either node
E or node F is shortest