Page 374 -

354 CHAPTER 8 NETWORK MODELS

NOTES AND COMMENTS

1 Many applications of the shortest-route algorithm 2 In some applications, the value associated with an
involve criteria such as time or cost instead of arc may be negative. For example, in situations
distance. In these cases, the shortest-route where cost is the criterion, a negative arc value
algorithm provides the minimum-time or would denote a negative cost; in other words, a
minimum-cost solution. However, since the profit would be realized by traversing the arc. The
shortest-route algorithm always identifies a shortest-route algorithm presented in this section
minimum-value solution, it would not make sense can only be applied to networks with nonnegative
to apply the algorithm to problems that involve a arc values. More advanced texts discuss algorithms
profit criterion. that can solve problems with negative arc values.

8.2 Minimal Spanning Tree Problem

In network terminology, the minimal spanning tree problem involves using the arcs of
the network to reach all nodes of the network in such a fashion that the total length of
all the arcs used is minimized. To better understand this problem, let us consider the
communications system design problem encountered by a regional computer centre.
The Southwestern Regional Computer Centre must have special computer commu-
nications lines installed to connect five satellite users to a new central computer system.
The telephone company will install the new communications network. However, the
installation is an expensive operation. To reduce costs, the centre’s management group
wants the total length of the new communications lines to be as short as possible.
Although the central computer could be connected directly to each user, it appears to
be more economical to install a direct line to some users and let other users tap into the
system by linking them with users already connected to the system. The determination
of this minimal length communications system design is an example of the minimal
spanning tree problem. The network for this problem with possible connection alter-
natives and distances is shown in Figure 8.13. An algorithm that can be used to solve
this network model is explained in the following subsection.

Figure 8.13 Communications Network for the Regional Computer System

5
40
2 50 30
20
40 3
Regional
computer 1 30 10 40
centre
4 30

40 20
km of
communication
lines required 6
between locations

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.