Edmonds–Karp algorithm

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.