The Ford-Fulkerson Method | Algorithms II

The Ford-Fulkerson method is the foundational approach to solving the maximum-flow problem. It repeatedly finds paths from source to sink in the residual network and augments flow along them.

Core Idea

Start with zero flow. While an augmenting path (a simple path from $s$ to $t$ in the residual network $G_f$ ) exists, compute the bottleneck capacity along that path and push that amount of additional flow through every edge of the path.

Algorithm

FORD-FULKERSON(G, s, t):
    initialise flow f = 0 on all edges
    while there exists an augmenting path p in G_f:
        c_f(p) = min{ c_f(u, v) | (u, v) on p }
        for each edge (u, v) on p:
            if (u, v) in G.E:
                f(u, v) = f(u, v) + c_f(p)
            else:
                f(v, u) = f(v, u) - c_f(p)
    return f

When processing a residual edge that corresponds to a reverse direction, we decrease the forward flow (cancelling it), effectively “pushing flow backwards”.

Finding Augmenting Paths

Any graph search (DFS or BFS) on $G_f$ suffices. DFS may produce long, meandering paths; BFS finds shortest augmenting paths (in number of edges) and leads to the Edmonds-Karp variant.

Worked Example

Consider this network (edge labels show capacity):

    s ---10--> a ---3--> b ---7--> t
    |         |                  ^
    +----5--->b-----------------+
              a ---8--> t

Initial flow is zero everywhere. Residual network equals original.

Iteration 1: augmenting path $s \to a \to t$ , bottleneck $\min(10, 8) = 8$ . Flow: $f(s, a) = 8$ , $f(a, t) = 8$ . Residual: $(s, a)$ has residual 2, $(a, t)$ has residual 0, plus reverse edges $(a, s)$ capacity 8, $(t, a)$ capacity 8.

Iteration 2: augmenting path $s \to b \to t$ , bottleneck $\min(5, 7) = 5$ . Flow: $f(s, b) = 5$ , $f(b, t) = 5$ . Residual: $(s, b)$ has residual 0, $(b, t)$ has residual 2.

Iteration 3: augmenting path $s \to a \to b \to t$ , bottleneck $\min(2, 3, 2) = 2$ . Flow: $f(s, a) = 10$ , $f(a, b) = 2$ , $f(b, t) = 7$ . Residual: $(s, a)$ saturated, $(b, t)$ saturated, $(a, b)$ has residual 1.

No further augmenting paths exist. Maximum flow value $= 8 + 5 + 2 = 15$ .

The residual network at termination shows $s$ can only reach $\{a\}$ ; sink $t$ is unreachable. This partition is a minimum cut (see Max-Flow Min-Cut Theorem).

Termination and Running Time

Integer Capacities

If all capacities are integers, each augmentation increases $|f|$ by at least 1. Since $|f| \le$ total capacity out of $s$ , at most $|f^*|$ augmentations, where $f^*$ is the maximum flow. Cost per augmentation: $O(|E|)$ for DFS/BFS. Total: $O(|E| \cdot |f^*|)$ .

This is pseudopolynomial: the running time depends on the numeric value of the capacities, not just the graph size. For a network where $|f^*|$ is large (e.g. capacity $10^9$ ), this is impractical.

Irrational Capacities

With irrational capacities, Ford-Fulkerson with arbitrary path selection may fail to terminate. The flow can increase by ever-smaller increments in a non-convergent series. This is a theoretical concern only; all practical implementations use rational capacities.

Practical Considerations

Always use BFS (Edmonds-Karp) or Dinic’s algorithm. Never use arbitrary DFS path selection in real code. See Edmonds-Karp Algorithm for the polynomial-time variant.

Summary

Aspect	Detail
Core operation	Find augmenting path in $G_f$ , push bottleneck capacity
Flow cancellation	Reverse edges in $G_f$ allow “undoing” flow
Termination (integer)	$O(\lvert E \rvert \cdot \lvert f^* \rvert)$ — pseudopolynomial
Termination (irrational)	Not guaranteed
Key insight	Residual network encodes all possible flow adjustments

Past Tripos: y2024p1q9, y2022p2q7.