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 in the following screen.
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 in mimimum spanning tree problems.
The eight branches that should be used are marked with a Y and the minimum cost of connecting the nine nodes is 178. A table displaying the order in which the branches were added can be displayed as illustrated in the following screen.
A shortest path example is given below.
We want to find the shortest path and distance from one point to another. The data screen is shown in the preceding illustration. Notice that it is possible to specify the origin and destination. If you leave it at 0, 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, the distance from node j to node i is set equal to the distance form node i to node j. For example, the distance from node 2 to node 1 is set to 20.
The solution is as follows.
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 follows. To see the path set the values for the start and end above the data.
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 0 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 oftentimes more than one solution exists. Also, there may be more than one way to derive the solution. The maximal flow is 61 and the flows along the branches can be seen in the figure.
The iterations are given in the following screen. Please note that there are generally several different iteration steps that could be taken to arrive at the same maximal flow.
