Although Dynamic Programming methods of Chapter 9 are usually more efficient, the problem of finding a shortest path from a given origin s to a destination t in a graph with no negative dicycles can easily be represented as a minimum cost flow problem. Using arc lengths as costs, it is only necessary to make s a node with supply

= 1, t a node with demand = 1, and treat all other nodes as transshipment.

(a) Illustrate and justify how this produces an optimal path by formulating the problem of finding a shortest path from s = 3 to t = 5 in the digraph of Exercise 10-1.

(b) Do part

(a) for a path from s = 1 to t = 5 in the digraph of Exercise 10-2.