# 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 #### kindsonthegenius

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

View all posts by kindsonthegenius →