Freddy Duarte

SUMMARY OF METHODOLOGY FOR MINIMAL SPANNING TREE NETWORK

A minimal spanning tree problem is typified by a collection of nodes and branches wherein nodes represent locations in geographical space. Initially these nodes are totally disconnected. The branches represent potential connections between pairs of nodes. The objective in this problem is to select a set of branches that will connect all the nodes (every node is reachable from every other node, either directly or indirectly) with as small a total length of connections as possible. This set of connections is referred to as the spanning tree.

An efficient methodology when data are presented in network format is as follows:

1. Begin by selecting any of the nodes and designating it to be a part of the connected set. Initially this will be the only connected node.
2. Scan all the unconnected nodes that can be reached directly from any of the connected nodes, and identify the one that is closest to any of the connected nodes. Designate this node as another of the connected nodes. (If there is a tie for the closest, select any of the tied nodes)
3. Repeat Step 2 until all nodes are connected.

SUMMARY OF METHODOLOGY FOR SHORTEST ROUTE NETWORK

A shortest route problem is typified by a collection of nodes and branches wherein nodes represent locations in geographical space and branches represent the travel distance (or perhaps travel time, or travel cost) between nodes. A shortest route problem will have a designated starting node and a designated destination node.

To find the shortest route from the starting node to the destination node, begin by establishing a node labeling system. The first term of the label represents the distance from the starting node to the node in question and the second term of the label represents the prior node traversed in getting to the node in question. Labels will be designated as either temporary labels or permanent labels. Temporary labels are subject to change if the distance can be improved; permanent labels are not subject to change. An efficient methodology is as follows:

1. Create a temporary label for the starting node with a distance of zero and no prior node traversed.
2. Scan all temporary labels to find the one with the smallest distance. Designate this as a permanent label. If there is a tie for smallest distance among temporary labels, select any of the tied nodes. (Note: At the beginning of the problem solution, the only temporary label is the label on the starting node, therefore it will always become the first permanent label created.)
3. Identify all non-permanently labeled nodes that can be reached directly (i.e., directly linked) from this newly created permanently labeled node of Step 2. Subject each of these nodes to the following tests:
   • For any of these reachable nodes that do not yet have a temporary label, create one in the following manner:
     The distance on this temporary label will be the distance on the permanent label you created in Step 2 plus the distance from that Step 2 node to the node currently being labeled. The prior node on this temporary label will be the node you identified in Step 2 as a new permanently labeled node.
   • For any of these reachable nodes that do have a temporary label, do the following:
     Compare its current temporary label distance to the distance of the Step 2 permanent label plus the distance from the Step 2 node to this node in question. If the distance on the temporary label is less this total, do not alter the temporary label. If the distance on the temporary label is greater than this total, change the temporary label. Its new distance will be this total, and its prior node will be the node whose label was made permanent in Step 2. (Note: Occasionally the distance on the temporary label may be exactly equal to this total that you are comparing. When this happens there may be alternate shortest routes to this node. In a case like this you can keep the old temporary label and also create and attach another temporary label. Both temporary labels will have the same distance, but different prior nodes. These will help you trace out the alternate optimal routes at the conclusion of the problem.)
4. If your ultimate destination node does not yet have a permanent label, return to Step 2
5. If your ultimate destination node does have a permanent label, you have found the shortest distance to this node, and can trace out its route.

SUMMARY OF METHODOLOGY FOR MAXIMAL FLOW NETWORK

A maximal flow problem is typified by a collection of nodes and branches wherein nodes represent locations in geographical space and branches represent connections between those locations. A maximal flow problem will have a designated starting node (often referred to as a source node) and a designated destination node (often referred to as a sink node). This type of problem will have movement, or flow, of some commodity through the system from the source node to the sink node. The objective is to determine the maximum amount of traffic that can flow from the source to the sink in a specified period of time. Since flow capacity along a branch will depend upon the direction of flow, each branch in the network displays the flow capacity with two numbers (each represents capacity for flow out of the adjacent node).

An efficient methodology for the maximal flow problem is as follows:

1. Select a path that leads from source to sink and has some capability to accept flow; and assign the maximum flow possible to that path (the maximum flow will be equal to the smallest capacity from among the branches that make up that path).
2. Reduce the remaining capacity on the front end of each branch along the path by the amount of flow assigned to the path in Step 1. Increase the remaining capacity on the back end of each branch along the path by the same amount.
3. Repeat Steps 1-2 until there are no more paths leading from the source to the sink that have the capability to accept flow. The maximum flow will be the sum of all the path assignments made in Step 1.