Example Problem Solution

[Page 293 ( continued )]

The following example illustrates the solution methods for the shortest route and minimal spanning tree network flow problems.

Problem Statement

A salesman for Healthproof Pharmaceutical Company travels each week from his office in Atlanta to one of five cities in the Southeast where he has clients . The travel time (in hours) between cities along interstate highways is shown along each branch in the following network:

1. Determine the shortest route from Atlanta to each of the other five cities in the network.

2. Assume that the network now represents six different communities in a city and that the local transportation authority wants to design a rail system that will connect all six communities with the minimum amount of track. The miles between each community are shown on each branch. Develop a minimal spanning tree for this problem.

Solution

Step  1.

(Part A): Determine the Shortest Route Solution

---

[Page 294]

1. Permanent Set	Branch	Time
{1}	12
	13	5
	14	7
2. Permanent Set	Branch	Time
{1, 2}	13
	14	7
	25	11
3. Permanent Set	Branch	Time
{1, 2, 3}	14
	25	11
	34	7
4. Permanent Set	Branch	Time
{1, 2, 3, 4}	45	10
	46
5. Permanent Set	Branch	Time
{1, 2, 3, 4, 6}	45
	65	13
6. Permanent Set
{1, 2, 3, 4, 5, 6}

The shortest route network follows :

Step  2.

(Part B): Determine the Minimal Spanning Tree

1. The closest unconnected node to node 1 is node 2.

2. The closest unconnected node to 1 and 2 is node 3.

3. The closest unconnected node to 1, 2, and 3 is node 4.

4. The closest unconnected node to 1, 2, 3, and 4 is node 6.

5. The closest unconnected node to 1, 2, 3, 4, and 6 is node 5.

The minimal spanning tree follows; the shortest total distance is 17 miles: