(Relation of Primal-Dual and Ford-Fulkerson) Consider the Ford-Fulkerson algorithm for the max-flow problem, where bij = 0 for all (i, j) ∈ A. Show that the method can be interpreted as an application of the primal-dual method to the minimum cost flow formulation of the max-flow problem of Example 1.3 in Section 1.2, starting with p = 0 and x = 0 [except for
the flow of the artificial arc (t, s), which must be at its upper bound to satisfy CS]. Show in particular that all iterations of the primal-dual method start at node s and terminate with an augmentation along a path ending at node t. Furthermore, the method executes only one price change, which occurs after a minimum cut is identified. The last iteration consists of an augmentation along the artificial arc (t, s)