= Edmonds–Karp algorithm
{c}
{wiki}
This <maximum flow> algorithm repeatedly augments along a shortest residual path found by <Breadth-first search>. Residual distances from the source never decrease. If the same arc becomes saturated again after being restored by a reverse augmentation, the distance to its tail has increased by at least two. Thus each arc is critical only $O(|V|)$ times, yielding $O(|V||E|)$ augmentations. Each search costs $O(|E|)$, so the total time is $O(|V||E|^2)$. Termination with no residual source-sink path supplies a <max-flow min-cut theorem> certificate.
Back to article page
