(k Shortest Node-Disjoint Paths) The purpose of this exercise, due to Casta˜non [1990], is to formulate a class of multiple shortest path problems and to indicate the method for their solution. Consider a graph with an origin 1, a destination t, and a length for each arc. We want to find k paths from 1 to t which share no node other 1 and t and which are such that the sum of the k path lengths is minimum. Formulate this problem as a minimum cost flow problem. (For an auction algorithm that solves this problem, see Bertsekas and Casta˜non [1993c].) Hint: Replace each node i other than 1 and t with two nodes i and i and a connecting arc (i, i ) with flow bounds 0 ≤ xii ≤ 1.