Page 367 -

SHORTEST-ROUTE PROBLEM 347

At any step of the labelling procedure, a node is said to be either labelled or
unlabelled. A labelled node is any node for which we have identified a path from
node 1 to that node, and an unlabelled node is any node for which a path has not yet
been identified. A labelled node is also said to be either permanently or tentatively
labelled. Whenever the algorithm has determined the shortest distance from node 1
to a particular node, the node is said to have a permanent label. If, however, the
shortest distance from node 1 to a particular labelled node has not yet been
determined, the node is said to have a tentative label. Now let us show how labels
are calculated and how the labelling process can be used to determine the shortest
route to each of the nodes in the network.
We begin the labelling process by giving node 1 the permanent label [0,S]. The 0
indicates that the distance from node 1 to itself is zero and the S identifies node 1 as the
starting node. To distinguish between tentatively and permanently labelled nodes, we
use dark shading for all permanently labelled nodes in the network. In addition, an
arrow indicates the permanently labelled node being investigated at each step of the
labelling algorithm. The initial identification of GDA’s network is shown in Figure 8.3
when only node 1 is permanently labelled. The reason we distinguish between perma-
nent and tentative labels is because we are adopting an iterative approach and will be
comparing different nodes through the network in our search for the shortest node.
Consider node 4, for example. To reach this node from node 1 there are several
possibilities: node 1–2–4; 1–3–5–4; 1–2–7–4 and so on. We need to be able to distin-
guish between possible (tentative) nodes and those which are optimal (permanent).
To perform the first step or iteration of the labelling procedure, we must consider
every node that can be reached directly from node 1; so, we look first at node 2 and
then at node 3. We see that the direct distance from node 1 to node 2 is 15 km. So,
node 2 can be tentatively labelled [15, 1], with the second number indicating that the
preceding node on this route to node 2 is node 1. Next, we consider node 3 and find
that the direct distance from node 1 to node 3 is 10km. So, the tentative label at node
3 is [10, 1]. Figure 8.4 shows the results so far with nodes 2 and 3 tentatively labelled.
Refer to Figure 8.4. We now consider all tentatively labelled nodes and identify
the node with the smallest distance value in its label; so, node 3 with a travel distance
of 10km is selected. Could we get to node 3 following a shorter route? Because any
other route to node 3 would require passing through other nodes, and because the
distance from node 1 to all other nodes is greater than or equal to ten, a shorter

Figure 8.3 Initial Network Identification for GDA’s Shortest-Route Problem

7
17
5
2 6
6
15 4

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

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.