エドモンズ・カープのアルゴリズム

エドモンズ・カープのアルゴリズム（英: Edmonds-Karp algorithm）は、フローネットワークの最大フロー問題を解くフォード・ファルカーソンのアルゴリズムの実装の一種であり、<math>O(VE^2)</math> の計算量である。<math>O(V^3)</math> のrelabel-to-front アルゴリズムに比べると漸近的に遅いが、（辺の少ない）疎なグラフでは速い。このアルゴリズムは1970年にロシア人科学者 Dinic が発表し、それとは独立に1972年にジャック・エドモンズとリチャード・カープが発表した（発見はこちらの方が早かった）。Dinic のアルゴリズムには追加の技法が含まれており、計算量は <math>O(V^2E)</math> となっている。