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.

There are several $s$-$t$-augmenting paths, but let’s assume we decide on the path s -> a -> b -> t. The flow that we can push through this path is $2$, or the minimum of the edge capacities on it. After augmenting our flow in that way, we’ll arrive at the following network:

At this point, no further paths from $s$ to $t$ exists upon which every edge still has free capacity. However, the flow we’ve found so far is not a maximum flow. This means that our simple strategy of finding augmenting paths was not good enough.

The problem that we ran into here is that we made an incorrect decision by pushing two units of flow from $a$ to $b$ ...