Ford–Fulkerson method

The Ford–Fulkerson method is a technique for solving the maximum flow problem. The input is a flow network, $G_0 = (V, s, t, c)$. Then the algorithm proceeds as follows:

1. Start with the empty flow, $f_0(u, v) = 0$ for all $u, v \in V$. The corresponding residual network is then equivalent to the original flow network, $G_0 = (V, s, t, c)$.
2. Find an augmenting path. Let $c_m$ be the minimum residual capacity along the augmenting path. Push $c_m$ units of flow along the path, adding to the flow $f_i$ to give an augmented flow $f_{i+1}$. Corresponding to the augmented flow is a new residual network, $G_{i+1}$.
3. Repeat step 2 with the new flow and new residual network until an augmenting path can no longer be found. The final flow $f_n$ is a max flow.

Correctness

If the algorithm terminates, then no augmenting path remains. By the augmenting path theorem, the flow $f_n$ obtained is maximal.

If the capacities are finite and integral, then the algorithm is guaranteed to terminate. It is not hard to see that an invariant of the algorithm is that the residual capacities are all integral after each augmenting step. Therefore $c_m \geq 1$ in each step, and the flow so far increases by at least one unit in each step. The algorithm must then terminate after no more than $M$ steps, where $M$ is the value of the max flow. A similar argument applies when all edge weights are rational.

On the other hand, the algorithm is not guaranteed to terminate when the edge weights are allowed to be irrational.

Complexity

In step 2, we have a choice in how to find the augmenting path. The overall running time of the algorithm depends on the heuristic used to choose the path. In the most common choice of heuristic, known as the Edmonds–Karp algorithm, we always choose the shortest augmenting path using breadth-first search. (Note that the capacities are not lengths; each edge has length 1!) It is easy to see that the running time of such an approach is $O((E+V)M)$. Under a more sophisticated analysis, we can derive the bound $O(VE^2)$, which is independent of the edge capacities.

Other heuristics are possible. We could for example use depth-first search to find an augmenting path, which also gives an $O((E+V)M)$ algorithm. Another possibility is to use a modification of Dijkstra's algorithm to find an augmenting path of maximal value, i.e., that maximizes $c_m$. In this case we have the bound $O((E + V \log V)M)$.

A more sophisticated approach, known as Dinic's algorithm, runs in $O(V^2 E)$ time, which can be sped up to $O(V E \log V)$ using link/cut trees.