the Ford-Fulkerson method
/ FORD-FULL-ker-sun /
The most natural plan for maximizing flow is also the most direct: start with nothing flowing, then keep finding a route from source to sink that still has room and pour more along it, stopping only when no such route remains. That plan, made precise with residual graphs so it can also undo earlier choices, is the Ford-Fulkerson method. It is less a single algorithm than a template, because it does not say which route to pick.
The method: initialize f = 0 on every edge. While there is an augmenting path P from s to t in the residual graph Gf, find P, compute its bottleneck (the minimum residual capacity along it), and augment the flow by that amount along P. When no augmenting path exists, return f. Each augmentation strictly increases the flow value, and when it halts, the augmenting-path theorem guarantees f is a maximum flow; the vertices still reachable from s define a minimum cut, certifying optimality. With integer capacities, every augmentation raises the value by at least 1, so the method runs in at most |f*| augmentations, where |f*| is the max-flow value — giving a running time of O(E * |f*|).
Ford-Fulkerson is the conceptual ancestor of all max-flow algorithms and the cleanest setting in which to understand augmenting paths and the max-flow min-cut theorem. But 'method' is the honest word: it leaves the path choice open, and that choice matters enormously. With unlucky choices, the O(E * |f*|) bound can be terrible (think capacities in the millions but a tiny graph), and with irrational capacities and a bad choice rule it can even fail to terminate, converging to a value below the true maximum. Edmonds-Karp fixes this by always choosing a shortest augmenting path, recovering a capacity-independent polynomial bound.
The classic bad case: vertices s, a, b, t with s->a, s->b, a->t, b->t all capacity 1000 and a middle edge a->b of capacity 1. Picking augmenting paths that zig-zag through the middle edge augments by just 1 each time, taking ~2000 iterations; picking the two obvious direct paths finishes in 2. Same method, wildly different cost — because the method leaves the choice unspecified.
Ford-Fulkerson is a template; its speed lives or dies on the path-selection rule it deliberately leaves open.
The O(E * |f*|) bound depends on the flow value, not just the graph size — so huge capacities make it slow, and with irrational capacities a poor path rule may never terminate. Use Edmonds-Karp or Dinic when you need a guarantee.