4.II.20D
Part IB, 2005
Describe the Ford-Fulkerson algorithm for finding a maximal flow from a source to a sink in a directed network with capacity constraints on the arcs. Explain why the algorithm terminates at an optimal flow when the initial flow and the capacity constraints are rational.
Illustrate the algorithm by applying it to the problem of finding a maximal flow from to in the network below.