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.

augment(f, P) Set b = bottleneck(P, f) for each edge (u, v) ∈ P if (u, v) is a forward edge then increase f(e) in G by b else (u, v) is a backward edge reduce f(e) in G Endif Endfor Return(f)

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.

Max-Flow Initially set f(e) = 0 for all e in G while there is an s-t path in the residual graph Gf Let P be a simple s-t path in Gf f' = augment(f, P) Update f to be f' Update the residual graph Gf to be Gf' Endwhile Return f

Listing 1.1: The Max-Flow Algorithm

This Max-Flow algorithm is the Ford-Fulkerson algorithm.