In computer science, the Edmonds–Karp algorithm is an implementation of the Ford–Fulkerson method for computing the maximum flow in a flow network in <math>O(|V||E|^2)</math> time. The algorithm was first published by Yefim Dinitz in 1970, and independently published by Jack Edmonds and Richard Karp in 1972. Dinitz's algorithm includes additional techniques that reduce the running time to <math>O(|V|^2|E|)</math>. A proof outline using these properties is as follows:
The proof first establishes that distance of the shortest path from the source node to any non-sink node in a residual flow network increases monotonically after each augmenting iteration (Lemma 1, proven below). Then, it shows that each of the <math>|E|</math> edges can be critical at most <math>\frac{|V|}{2}</math> times for the duration of the algorithm, giving an upper-bound of <math>O\left( \frac{|V||E|}{2} \right) = O(|V||E|)</math> augmenting iterations. Since each iteration takes <math>O(|E|)</math> time (bounded by the time for finding the shortest path using Breadth-First-Search), the total running time of Edmonds-Karp is <math>O(|V||E|^2)</math> as required.