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

Listing 1.1: The Max-Flow Algorithm

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

Watch the Video Explanation

Admin bar avatar

kindsonthegenius

Kindson Munonye is currently completing his doctoral program in Software Engineering in Budapest University of Technology and Economics

View all posts by kindsonthegenius →

Leave a Reply

Your email address will not be published. Required fields are marked *