フォード・ファルカーソンのアルゴリズム
グラフ G ( V , E ) {\displaystyle G(V,E)} にて、 u {\displaystyle u} から v {\displaystyle v} への容量 c ( u , v ) {\displaystyle c(u,v)} でフロー f ( u , v ) = 0 {\displaystyle f(u,v)=0} とする。ここで、始点 s {\displaystyle s} から終点 t {\displaystyle t} への最大フローを求める。最終的に、次のような状態となる。
f ( u , v ) ≤ c ( u , v ) {\displaystyle \ f(u,v)\leq c(u,v)} : u {\displaystyle u} から v {\displaystyle v} へのフローは容量を超えない。
f ( u , v ) = − f ( v , u ) {\displaystyle \ f(u,v)=-f(v,u)} : u {\displaystyle u} と v {\displaystyle v} の間の総フローの性質。
フォード・ファルカーソンのアルゴリズム(英: Ford-Fulkerson algorithm)とは、フローネットワークにおける最大フローを求めるアルゴリズムである。レスター・フォード Jr.(英語版、ドイツ語版、フランス語版、ロシア語版) と デルバート・ファルカーソン(英語版、ドイツ語版、スペイン語版、フランス語版) にちなんで命名されたもので、1956年に発表された。フォード・ファルカーソンのアルゴリズムの特殊版であるエドモンズ-カープアルゴリズムも「フォード・ファルカーソン」と呼ばれることがある。
このアルゴリズムの背景にある考え方は非常に単純である。始点から終点への経路があって、経路上の各辺に容量の空きがあるとき、その経路を使って流れを作ることができる。これを経路が見つかるたびにくりかえす。容量に空きがある経路を「増加道; augmenting path」と呼ぶ。