We now present the Ford-Fulkerson algorithm and a simple explanation. To follow this tutorial, you need to understand:
Take some time to review these prerequisite topics.
Before we do that, recall the definition of bottleneck. A bottleneck(P, f) is defined on a path P(a simple path) on the residual graph as the minimum residual capacity on any edge of P with respect to the flow f.
An s-t path in the residual graph is also known as an augmenting path.
The Ford-Fulkerson algorithm proceeds by successively augmenting each edge on the path until no path exists between s and t in the residual graph.
The augment procedure is given below.
Listing 1.0: The augment procedure
Note that the augment procedure is performed in the residual graph to produce a flow in G. Now this augmentation procedure has to be repeated until we obtain the max-flow for G. This is a point where we can no longer find an s-t path in the residual graph.
The algorithm for finding the max-flow is given in Listing 1.1.
Listing 1.1: The Max-Flow Algorithm
This Max-Flow algorithm is the Ford-Fulkerson algorithm.