Page 371 -

SHORTEST-ROUTE PROBLEM 351

Figure 8.10 GDA’s Network with a Permanent Label at Node 4

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

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

We now have only two remaining non-permanently labelled nodes. Because the
distance value at node 4 is smaller than that at node 7, node 4 becomes the new
permanently labelled node. Because node 7 is the only non-permanently labelled
node that can be reached directly from node 4, we compare its distance value of 22
with the sum of the distance value at node 4 and the direct distance from node 4 to
node 7, that is, 18 + 5 ¼ 23. Because the [22, 6] tentative label at node 7 is smaller,
it remains unchanged. Figure 8.10 shows the network at this point.
Because node 7 is the only remaining node with a tentative label, it is now perma-
nently labelled. Figure 8.11 shows the final network with all nodes permanently labelled.
We can now use the information in the permanent labels to find the shortest route
from node 1 to each node in the network. For example, node 7’s permanent label tells
us the shortest distance from node 1 to node 7 is 22km. To find the particular route
that enables us to reach node 7 in 22km, we start at node 7 and work back to node 1.
Node 7’s label gives us the next direct link – node 6 – and node 6’s label indicates

Figure 8.11 GDA’s Network with All Nodes Permanently Labelled

[22, 6]
7
17
[13, 3]
5
2 6
6
[18, 5]
15 4
3 6
[0, S] 4
2
[16, 5]
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.