| 1. Introduction | 2. Example | 3. Main Menu | 4. Printing | 5. Graphs | 6. Modules |
Three models are available in this module - minimum spanning tree, shortest path and maximal flow. We will use the following diagram for each of our three examples. In order to start any of the three submodules it is necessary to indicate the number of branches. In our example there are 14 branches. In order to enter each branch its starting node and its ending node must be given.
In the minimum spanning tree we try to connect n nodes to each other using n-1 of the available arcs. Arcs have costs and the goal is to minimize the total cost. The data and solution to our example appear below.
The data is the standard data of the arc or branch expressed as from and to node numbers and the cost of using the arc. Above the data is a box that enables the user to specify the starting node number. If you leave it as 0 the lowest node number will be used. Of course, the total cost is independent of the starting node but the actual arcs used might vary (if there are alternate solutions as there are in this example).
The eight branches which should be used are marked with a Y and the minimum cost of connecting the 9 nodes is 178. A table displaying the order in which the branches were added can be displayed as illustrated below.
We want to find the shortest path and distance from one point to another. The data screen is shown above. Notice that it is possible to specify the origin and destination. If you leave it blank then the program will find the shortest path from the minimum node number to the maximum node number (1 to 9 ) in this example.
Above the data the network can be set to be directed or undirected. If it is undirected then by the distance form node j to node i is set equal to the distance form node i to node j. For example, the distance from node to node 1 is set to 20.
The solution appears below.
Four branches should be included in the shortest path creating the path 1-3-6-8-9 with a total distance of 113. In addition, the program computes the minimum total distance from every node to every other node as shown below.
In this situation we want to maximize the flow from the beginning (source) to the end (sink). The number along each arc represents its capacities and the second number represents its reverse capacity (capacity in the opposite direction). At the top the source and sink can be set. If they are left at zero then the source is the node with the lowest number and the sink is the node with the highest number. Before presenting our solution we remind you that often times more than one solution exists and/or that there may be more than one way to derive the solution. The solution to our example appears below.
The maximal flow is 61 and the flows along the branches can be seen in the figure.
The iterations are given below. Please note that there are generally several different iteration steps that could be taken to arrive at the same maximal flow.
| 1. Introduction | 2. Example | 3. Main Menu | 4. Printing | 5. Graphs | 6. Modules |
 |
©
Prentice-Hall, Inc. A Simon & Schuster Company Upper Saddle River, New Jersey 07458 |