Edmonds-Karp Algorithm

Recall the Ford-Fulkerson method: while there is an augmenting path from the source to the sink in the residual graph, push the bottleneck amount of flow along it and repeat. Ford-Fulkerson never said which augmenting path to pick — and that choice is left wide open.

Edmonds-Karp is exactly Ford-Fulkerson with one rule added: always choose the augmenting path with the fewest edges. The easiest way to find the shortest path (in number of edges) is breadth-first search (BFS) from the source.

That is the only change. Everything else — residual capacities, backward edges, bottlenecks, the max-flow min-cut guarantee — is identical to the Ford-Fulkerson topic. If you haven't read that one yet, start there; this page assumes it.

Picking any augmenting path (for example with DFS) can be slow. Imagine two big pipes of capacity 1000 joined by a tiny middle pipe of capacity 1. A careless DFS might keep choosing a zig-zag path that runs through the tiny pipe, pushing just 1 unit at a time and looping up to 2000 times. The number of rounds then depends on the capacity numbers, not on the size of the graph — which is bad.

BFS avoids this trap. Because BFS always returns the augmenting path with the fewest edges, one can prove the shortest-path distance from the source to the sink never decreases, and each edge can only become the bottleneck a limited number of times. This gives a running time that depends only on the number of vertices and edges, never on how large the capacities are. That is the whole point of Edmonds-Karp.

Watch Edmonds-Karp run on the same network as the Ford-Fulkerson topic (source = node 0, sink = node 5), so you can compare them directly. Each edge is labelled flow / capacity. On every round BFS highlights the shortest augmenting path (amber, dashed), reports how many edges it uses and its bottleneck, then pushes that much flow. When BFS can no longer reach the sink, the total is the maximum flow, 23.

The only difference from Ford-Fulkerson is the highlighted line: the augmenting path is found with BFS, which returns the path using the fewest edges.

BFS itself costs O(V + E) per round. The key theorem is that BFS guarantees at most O(V · E) augmenting rounds, no matter how big the capacities are. Multiplying the two gives O(V · E²) total — a true polynomial bound that does not depend on the capacity values, unlike plain Ford-Fulkerson whose O(E · |f*|) can blow up when capacities are large.

Step through Edmonds-Karp at your own pace. Move forward and backward, play the animation, or reset. Notice how BFS consistently grabs the shortest available path each round on its way to the maximum flow of 23.