Implementation of Ford Fulkerson (Edmonds-Karp)

In this lesson, we’ll implement the Ford-Fulkerson method to solve maximum flow problems. We’ll select a variant of Ford-Fulkerson called Edmonds-Karp, which has a better worst-case runtime.

Implementation Notes

In principle, we’ll follow the general Ford-Fulkerson method:

1. Initialize a flow $f$ of value $0$.
2. Construct the residual network $G_f$.
3. Try to find an $s$-$t$-path in $G_f$.
4. • If there is such a path, augment the flow $f$ with it, then go to step $2$.
   • If there is no such path, return the flow $f$.

Edmonds-Karp’s only addition is that for step $3$, a breadth-first search is used to find an $s$-$t$-path in the residual network.

Our input flow network will be represented using the weighted adjacency list data structure, where the edge weights are the capacities. To simplify the implementation, we won’t explicitly construct the residual network. Instead, we’ll keep track of the flow $f(u, v)$ going through each edge. This is sufficient to compute residual capacities on the fly using the formula

$$c_f(u, v) = c(u, v) - f(u, v) + f(v, u).$$

Another technicality is that the residual network $G_f = (V, E_f, c_f)$ might contain edges that are not in the original graph. Here is a minimal example: