by 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.
