The Ford-Fulkerson Method

This lesson will cover a general, high-level strategy to compute maximum flows, called the Ford-Fulkerson method.

Description of the method

Given a flow network $G = (V, E, c)$, the Ford-Fulkerson method iteratively refines a flow $f$ in the graph, until it becomes a maximum flow.

In the beginning, the flow $f$ has value $0$, or, $f(u, v) = 0$ for all edges $(u, v) \in E$.

We then search for a path from $s$ to $t$ through which we can still push at least a single unit of flow. Such a path is called an augmenting path. We can use it to update our flow $f$ to a flow of higher value. We repeat this procedure until no augmenting path exists, at which point our flow $f$ is maximum.

A first attempt of finding augmenting paths

So, let’s look into how we can identify augmenting paths. The first approach might be to look for an $s$-$t$-path upon which each edge still has capacity remaining, or,

$$f(u, v) < c(u, v) \qquad \text{for all edges } (u, v) \text{ on the path}.$$

Let’s try this out in an example flow network.