Page 373 -

SHORTEST-ROUTE PROBLEM 353

direct distance from the new permanently labelled node to the node in
question. The preceding node value is set equal to the new permanently
labelled node. Go to step 3.
Step 5. The permanent labels identify both the shortest distance from node 1 to each
node and the preceding node on the shortest route. The shortest route to a
given node can be found by starting at the given node and moving backward
to its preceding node. Continuing this backward movement through the
The shortest-route network will provide the shortest route from node 1 to the node in question.
problem can also be
formulated and solved as This algorithm will determine the shortest distance from node 1 to each of the other
a transshipment problem. nodes in the network. Note that N–1 iterations of the algorithm are required to find
Simply set the supply at the shortest distance to all other nodes. If the shortest distance to every node is not
the start node and the
demand at the end node needed, the algorithm can be stopped when those nodes of interest have been
equal to 1. However, permanently labelled. The algorithm can also be easily modified to find the shortest
unlike the labelling distance from any node, say node k, to all other nodes in the network. To make such
algorithm, this approach a change, we would merely begin by labelling node k with the permanent label [0,S].
does not find the
shortest route from the Then by applying the steps of the algorithm, we can find the shortest route from
start node to every other node k to each of the other nodes in the network.
node. The Management Scientist software package can be used to solve small shortest-
route problems. Input for the programme includes the number of nodes, the number
For practise in using the
labelling algorithm to of arcs and the length of each arc. The output shown in Figure 8.12 provides the
solve a shortest-route shortest route from node 1 to node 7 for the GDA problem.
problem, try Problem 1.

Figure 8.12 The Management Scientist Solution for the GDA Shortest-Route Problem

**** NETWORK DESCRIPTION ****

7 NODES AND 10 ARCS

ARC START NODE END NODE DISTANCE
--- ---------- -------- --------
1 1 2 15
2 1 3 10
3 2 3 3
4 2 4 6
5 2 7 17
6 3 5 4
7 4 5 4
8 4 7 5
9 5 6 2
10 6 7 6

THE SHORTEST ROUTE FROM NODE 1 TO NODE 7
****************************************

START NODE END NODE DISTANCE
---------- -------- --------
1 3 10
3 5 4
5 6 2
6 7 6

TOTAL DISTANCE 22

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.