Page 369 -

SHORTEST-ROUTE PROBLEM 349

Figure 8.6 GDA’s Network with New Tentative Labels for Nodes 2 and 5

7
[13, 3] 17
[15, 1]
5
2 6
6
15 4

3 6
[0, S] 4
2
1
10 5
4
3 [14, 3]
[10, 1]

We next consider all tentatively labelled nodes in order to find the node with the
smallest distance value in its label. From Figure 8.6 we see that this is node 2 with a
distance of 13km. Node 2 is now permanently labelled because we know that it can be
reached from node 1 in the shortest possible distance of 13km by going through node 3.
The next step or iteration begins at node 2, the most recently permanently labelled
node. As before, we consider every non-permanently labelled node that can be reached
directly from node 2; that is, nodes 4 and 7. Starting with the distance value of 13 in the
permanent label at node 2 and adding the direct distance from node 2 to both nodes 4
and 7, we see that node 4 can be reached in 13 + 6 ¼ 19km, while node 7 can be
reached in 13 + 17 ¼ 30km. So, the tentative labels at nodes 4 and 7 are as shown in
Figure 8.7.

Figure 8.7 GDA’s Network with a Permanent Label at Node 2 and New Tentative
Labels for Nodes 4 and 7

[30, 2]
7
17
[13, 3]
5
2 6
6
[19, 2]
15 4

[0, S] 3 4 6
2
1
10 5
4
3 [14, 3]
[10, 1]

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.