The Ford-Fulkerson Algorithm

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