Suppose that you use the network simplex algorithm to solve a problem created by a reduction from the single-source-shortest-paths problem as described in the proof of Property 22.29.
(i) Prove that the algorithm never uses a zero-cost augmenting path.
(ii) Show that the edge that leaves the cycle is always the parent of the destination vertex of the edge that is added to the cycle.
(iii) As a consequence of Exercise 22.138, the network simplex algorithm does not need to maintain edge flows. Provide a full implementation that takes advantage of this observation. Choose the new tree edge at random.
Exercise 22.138
Prove that the spanning tree described in the proof of Property 22.29 corresponds to a shortest-paths tree in the original network.