Page 372 -

352 CHAPTER 8 NETWORK MODELS

that node 5 is the next shortest-route link. Continuing this process, we note that we
reach node 5 from node 3 and, finally, that we reach node 3 from node 1. Therefore,
the shortest route from node 1 to node 7 is 1–3–5–6–7. Using this approach, the
following shortest routes are identified for the GDA transportation network:

Node Shortest Route from Node 1 Distance in km

2 1–3–2 13
3 1–3 10
4 1–3–5–4 18
5 1–3–5 14
6 1–3–5–6 16
7 1–3–5–6–7 22

Perhaps for a problem as small as the GDA problem you could have found the shortest
routes just as fast, if not faster, by inspection. However, when we begin to investigate
problems with 15 to 20 or more nodes, it becomes time-consuming to find the shortest
routes by inspection. In fact, because of the increased number of alternate routes in a
larger network, it is easy to miss one or more routes and come up with the wrong
answer. So for larger problems a systematic procedure such as the preceding labelling
procedure is required. Even with the labelling method, we find that as the networks
grow in size, it becomes necessary to implement the algorithm on a computer.
As we summarize the shortest-route algorithm, think of a network consisting of N
nodes. The following procedure can be used to find the shortest route from node 1
to each of the other nodes in the network.
Step 1. Assign node 1 the permanent label [0,S]. The 0 indicates that the distance from
node 1 to itself is zero and the S indicates that node 1 is the starting node.
Step 2. Calculate tentative labels for the nodes that can be reached directly from
node 1. The first number in each label is the direct distance from node 1 to
the node in question; we refer to this portion of the label as the distance
value. The second number in each label, which we refer to as the preceding
node value, indicates the preceding node on the route from node 1 to the
node in question; so, in this step the preceding node value is 1 because we
are only considering nodes that can be directly reached from node 1.
Step 3. Identify the tentatively labelled node with the smallest distance value, and
declare that node permanently labelled. If all nodes are permanently
labelled, go to step 5.
Step 4. Consider the remaining nodes that are not permanently labelled and that
can be reached directly from the new permanently labelled node identified
in step 3. Calculate new tentative labels for these nodes as follows:

a. If the node in question has a tentative label, add the distance value at
the new permanently labelled node to the direct distance from the new
permanently labelled node to the node in question. If this sum is less
than the distance value for the node in question, reset the distance
value for this node equal to this sum; in addition, set the preceding
node value equal to the new permanently labelled node that provided
the smaller distance. Go to step 3.
b. If the node in question is not yet labelled, create a tentative label by
adding the distance value at the new permanently labelled node to the

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.