Maximum Flow (Ford-Fulkerson)

Maximum Flow asks: how much can you push through a network of pipes from a source to a sink, given that every pipe has a capacity? The classic answer is Ford-Fulkerson — keep finding a path with room to spare and pour more flow down it until you cannot.

The slow way first

You might try to greedily shove flow down whatever path you see first and hope it works out. But a naive greedy choice can block itself: send too much down one route and you starve another, ending up below the true maximum with no obvious way to fix it.

The question to ask: when I am stuck, can I still find any route with leftover room? If yes, I am not done. The trick is to keep a residual graph that tracks remaining capacity (and lets flow be pushed back), and to repeatedly look for any path through it.

The idea: find a path, push the bottleneck, repeat

Walk this loop. Use BFS to find any path from s to t in the residual graph (edges that still have leftover capacity). The most you can add along that path is its bottleneck — the smallest remaining capacity on it. Push that much, update every edge on the path, and search again. When BFS finds no path, the flow you have accumulated is the maximum.

Using BFS (shortest augmenting path) is the Edmonds-Karp refinement — it guarantees the loop terminates in polynomial time, unlike picking paths arbitrarily.

Walk through it

Step through the animation. The first BFS path is S→A→T with bottleneck 2, so flow becomes 2. That saturates A→T, so the next BFS path is S→B→T, again bottleneck 2, taking flow to 4. Now every route out of S toward T is full, BFS returns nothing, and we stop with max flow = 4.

Pseudocode

flow = 0
loop:
    path, bottleneck = BFS for an s->t path with leftover capacity
    if no path:
        stop
    for each edge (u, v) on path:
        residual[u][v] -= bottleneck     # consume forward capacity
        residual[v][u] += bottleneck     # add a backward (residual) edge
    flow += bottleneck
return flow

The Python solution

def max_flow(graph, s, t):
    flow = 0
    while True:
        path, bottleneck = bfs(graph, s, t)
        if not path:
            break
        for u, v in path:
            graph[u][v] -= bottleneck   # use forward capacity
            graph[v][u] += bottleneck   # add residual edge
        flow += bottleneck
    return flow

• graph[u][v] holds the residual capacity left on edge u→v; bfs returns a path plus its bottleneck (the smallest residual along it).
• The while True loop is the Ford-Fulkerson core: keep augmenting until no path exists.
• if not path: break is the termination test — BFS could not reach the sink with any leftover capacity.
• Inside the for loop we subtract the bottleneck from each forward edge and add it to the reverse edge. That reverse (residual) edge is what lets a later path undo a bad earlier choice.
• flow += bottleneck accumulates the total; we return it once no augmenting path remains.

Complexity

Each BFS is O(E), and the number of augmenting paths is bounded — O(V·E) for Edmonds-Karp — giving the O(V·E²) bound. Storing the residual graph costs O(V + E).

When this pattern shows up

Practice