Ford-Fulkerson Method

The foundational augmenting-path scheme for computing maximum flow in a capacitated network.

The flow problem

Given a directed graph with edge capacities, a source s, and a sink t, a flow assigns a non-negative value to each edge not exceeding its capacity, with conservation at every node except s and t. The maximum-flow problem asks for the largest total flow leaving s. Ford-Fulkerson finds it by repeatedly pushing flow along augmenting paths.

Residual graph and augmenting paths

The residual graph records remaining forward capacity and, crucially, backward edges equal to the flow already sent, so the algorithm can reroute earlier decisions. An augmenting path is any s-to-t path with positive residual capacity; sending flow equal to its bottleneck increases total flow. Repeat until no augmenting path exists.

Termination and correctness

When no augmenting path remains, the flow is maximum by the max-flow min-cut theorem. With integer capacities the method terminates and runs in O(E * f) where f is the max-flow value, since each augmentation adds at least one unit. With irrational capacities and unlucky path choices it may not terminate, which motivates disciplined path selection.

def augment(residual, s, t):
    path = find_path(residual, s, t)   # any s-t path w/ residual > 0
    if not path:
        return 0
    bottleneck = min(residual[u][v] for u, v in path)
    for u, v in path:
        residual[u][v] -= bottleneck
        residual[v][u] += bottleneck    # backward edge
    return bottleneck

Why path choice matters

Choosing the shortest augmenting path by edge count gives Edmonds-Karp with a polynomial bound. Choosing fattest paths or using blocking flows leads to Dinic's algorithm. All are refinements of this same augmenting-path idea.