4.II.20D

Optimization
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 SS to TT in the network below.