Network Flow

Maximum flow answers: how much can a network route from a source s to a sink t without violating edge capacities? Edmonds-Karp solves it by repeatedly finding the shortest augmenting path with BFS.

Residual Graphs

For every edge with capacity c and current flow f, the residual graph holds two directions:

forward:  c − f     # how much more can be pushed
backward: f         # how much flow can be "undone"

An augmenting path is any path from s to t using edges with positive residual capacity. Pushing flow along it increases total flow; the bottleneck is the smallest residual capacity along the path.

Edmonds-Karp

while BFS finds a path s → t in the residual graph:
    bottleneck = min residual capacity on the path
    forward edges: flow += bottleneck
    reverse edges: flow -= bottleneck
    maxFlow += bottleneck
return maxFlow

Using BFS (rather than any path) means each augmentation uses the shortest remaining path, bounding the number of iterations to O(V·E) and the total runtime to O(V·E²) — polynomial, unlike the naive Ford-Fulkerson.

The Max-Flow / Min-Cut Theorem

A cut (S, T) splits nodes into two sides with s ∈ S, t ∈ T; its capacity is the sum of capacities of edges from S to T. The theorem states:

max flow = minimum cut capacity

The residual graph gives the proof: when no augmenting path remains, the set of nodes reachable from s in the residual graph forms a minimum cut, and the flow saturates exactly its crossing edges. Every unit of flow must cross any cut, so no flow can exceed any cut — and the algorithm achieves the minimum cut’s value.

What It Powers

• Bipartite matching — connect both sides through a super-source and super-sink with unit capacities; max flow = max matching.
• Max-flow-min-cost — add edge costs and extend to min-cost flow for assignment problems.
• Project selection and scheduling — closure problems reduce directly to min cut.
• Image segmentation — pixel regions become a graph whose min cut separates foreground from background.
• Data routing — computing the bottleneck capacity of a network.

Practice Trajectory

1. Build the residual graph by hand for a 4-node network and trace one BFS augmentation.
2. Implement Edmonds-Karp with adjacency lists of residual edge indices.
3. Verify the result equals a min cut you compute by enumeration.
4. Reduce bipartite matching to max flow and solve the assignment version.
5. Solve: project-selection and disjoint-path counting problems.

When It’s the Right Tool