the Edmonds-Karp algorithm
/ ED-mundz KARP /
Ford-Fulkerson works but leaves a dangerous freedom: which augmenting path to use. Edmonds-Karp removes the danger with one disciplined rule — always pick a shortest augmenting path, measured in number of edges. This single choice converts a method whose speed depends on capacity values into an algorithm with a clean polynomial guarantee that does not care how big the capacities are.
Edmonds-Karp is Ford-Fulkerson where each augmenting path is found by breadth-first search in the residual graph, so it has the fewest edges among s-t paths currently available. Running time is O(V * E^2). The reason it is polynomial rests on two facts you can state plainly. First, the BFS distance from s to any vertex in the residual graph never decreases as augmentations proceed (it is monotone non-decreasing). Second, each edge can become the bottleneck (the saturated, minimum-residual edge) of an augmenting path at most O(V) times, because between two such events the distance to one of its endpoints must strictly increase, and distances are bounded by V. There are E edges, so at most O(V * E) augmentations occur; each BFS costs O(E), giving O(V * E^2) overall — crucially, no dependence on the capacity magnitudes.
Edmonds-Karp is the first proof that maximum flow is solvable in strongly polynomial time, and it is simple to implement: just run BFS instead of arbitrary search inside the augmenting loop. In practice it is fast and reliable, though Dinic's algorithm improves the bound to O(V^2 * E) by augmenting along many shortest paths at once (a blocking flow per phase). The honest framing: Edmonds-Karp is not a new idea so much as a disciplined Ford-Fulkerson — the BFS rule is what tames the worst case the plain method suffers from.
On the bad 'middle edge of capacity 1' network where plain Ford-Fulkerson might take ~2000 augmentations, Edmonds-Karp's BFS finds the two short direct paths first (each 2 edges) and ignores the longer zig-zag through the middle, finishing in 2 augmentations regardless of the 1000-capacity edges.
Choosing the fewest-edge augmenting path (BFS) is the whole trick — it bounds augmentations by O(V*E), independent of capacities.
The O(V*E^2) bound is independent of capacity values, fixing Ford-Fulkerson's worst case. But it is still slower than Dinic O(V^2*E) on dense graphs, and far slower than specialized bipartite-matching bounds like Hopcroft-Karp.