Page 366 -

346 CHAPTER 8 NETWORK MODELS

Figure 8.1 Road Network for the GDA Shortest-Route Problem

Road distances
in km 7
17
5
2 6
6
15 4
6
3
4
2
1
10 4 5
GDA
office 3
Note: The length of each arc is not necessarily proportional
to the travel distance it represents.

transportation activities are substantial particularly given that many of the trips are
over very rough, undeveloped roads. For any given construction site, the travel
alternatives between the site and the office can be described by a network of roads,
streets and highways. The network shown in Figure 8.1 describes the travel alter-
natives to and from six of GDA’s newest construction sites. The circles or nodes of
the network correspond to the site locations. The roads, streets and highways appear
as the arcs in the network. The distances between the sites are shown above the
corresponding arcs. GDA would like to determine the routes or paths that will
minimize the total travel distance from the office to each site.

A Shortest-Route Algorithm
To solve GDA’s problem, we need to determine the shortest route from the GDA’s
office, node 1, to each of the other nodes in the network. The algorithm we present uses
a labelling procedure to find the shortest distance from node 1 to each of the other
nodes. As we perform the steps of the labelling procedure, we will identify a label
consisting of two numbers enclosed in brackets for each node. The first number in the
E. W. Dijkstre of the label for a particular node indicates the distance from node 1 to that node, while the
Netherlands proposed a
solution algorithm for the second number indicates the preceding node on the route from node 1 to that node.
shortest node problem in We will show the label for each node directly above or below the node in the network.
1959 For example, a label for a particular node might appear as shown in Figure 8.2.

Figure 8.2 An Example of a Node Label

Distance from node Preceding node on the
1 to this node is 20 route from node 1 to
this node is node 4

[20, 4]
Node label Node

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.