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.

Dinic’s Algorithm: When EK Is Too Slow

Edmonds-Karp re-runs a full BFS per augmentation. Dinic’s algorithm batches the work by building a level graph once per phase, then sending all shortest augmenting paths it can find through a single DFS:

1. BFS from s, labeling each node with its BFS depth → the level graph (only edges that go from depth d to d+1).
2. Blocking flow — DFS repeatedly from s to t, sending flow along level-graph edges until no s→t path remains. A current-edge pointer per node keeps the DFS from rescanning saturated edges, and dead ends are skipped so each DFS edge is examined O(1) times per phase.
3. Repeat (1)–(2) until s cannot reach t.

Each phase strictly increases the distance from s to t, so there are at most V phases; each phase costs O(V·E) worst case → O(V²·E) overall, and O(E√V) on bipartite matching. The practical gap is enormous: for dense graphs and matching problems, Dinic’s runs thousands of times faster than Edmonds-Karp — it is the default choice in competitive programming and library implementations.

level_graph = BFS(s)                          # phase
while level_graph contains t:
    while (path = DFS(s, t) in level_graph):  # blocking flow
        augment(path)
    level_graph = BFS(s)                      # next phase

The deeper insight: BFS-levels make the search monotone — every phase lengthens the shortest path, so the algorithm cannot get stuck cycling through the same short augmenting paths the way Ford-Fulkerson can on bad inputs.

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