エドモンズ・カープのアルゴリズム
このアルゴリズムはフォード・ファルカーソンのアルゴリズムとほぼ同じだが、増加道を探索するときの順序が定義されている点だけが異なる。それは、各辺が単位長としたときの幅優先探索である。 O ( V E 2 ) {\displaystyle O(VE^{2})} の実行時間は、各増加道の探索に O ( E ) {\displaystyle O(E)} の時間がかかり、 E {\displaystyle E} 個の辺のうち毎回少なくとも1つが飽和し、飽和した辺と始点を結ぶ増加道が前回より短くなることはなく、増加道の長さの上限は V {\displaystyle V} である。もう1つのこのアルゴリズムの特性として、最短増加道の長さは単調に増大する。アルゴリズムの妥当性の証明は書籍『アルゴリズムイントロダクション』(ISBN 476490408X) にある。