Problem 5 (25 points)

Consider the following network where the numbers represent actual distances between corresponding nodes.

(a) Use Dijkstras algorithm to find the shortest path(s) from O to T.

(b) Use the algorithm for the minimum spanning tree problem to determine the optimal spanning tree(s) and the total distance.

2. Assuming that the numbers on the arcs represent arc capacities,
   1. Use the augmenting path algorithm to find the maximum flow from O to T. Then determine the flows on the arcs that will render the maximum flow.
   2. Find a cut whose capacity equals the maximum flow.

3. Assume that the numbers on the arcs represent unit shipping costs and there is a source supplying 15 units at node O and a sink requiring 10 units at node T, while all other nodes are transshipment nodes. Also assume that, instead of being undirected, all arcs are directed according to edge set E = {OA, OC, OB, AC, BC, AD, CD, CE, BE, ED, DT, ET}. For example, there is an edge directed from node B to node C but not from C to B.

Write the flow balance equations for node O, C, and T of the corresponding minimum cost network flow problem.

A 4 D 6 6 4 8 4 E B 5