a) Use Dijkstras algorithm to find all shortest paths from O to T.

b) Use the algorithm for the minimum spanning tree problem to determine the minimum spanning tree(s).

c) Assume that the numbers on the arcs represent unit shipping costs and there is a source supplying 10 units at node O and a sink requiring 7 units at node T, while all other nodes are transshipment nodes. Write the flow balance equations for node O, C, and T of the corresponding minimum cost network flow problem. Assume that the arcs incident to node O are directed away from the node while the arcs incident to node T are directed toward T, e.g. arcs OA and GT exist but AO and TG do not exist. Also assume that the arcs incident to node C are directed: AC, OC, BC, CD, CE and CF.

Consider the following network where the numbers represent actual distances between corresponding nodes. 4 O 3 6 A B 4 3 55 160 5 D 5 E 1 3 F 6 5 3 2 G 3 T