The Algorithm Design Manual Second Edition

Analysis

The augmenting path algorithm above eventually converges on the the optimal

solution. However, each augmenting path may add only a little to the total flow,

so, in principle, the algorithm might take an arbitrarily long time to converge.

However, Edmonds and Karp

[EK72

] proved that always selecting a shortest

unweighted augmenting path guarantees that O(n

3

) augmentations suffice for op-

timization. In fact, the Edmonds-Karp algorithm is what is implemented above,

since a breadth-first search from the source is used to find the next augmenting

path.