フォード・ファルカーソンのアルゴリズム
フロー増加道をグラフ上で既に確立されているフローに追加していくと、最終的にフロー増加道が見つからなくなり、最大フローが得られる。しかし、そのような状態に到達するかどうかは不確実であり、単にアルゴリズムが完了した場合は解が正しいということしか保証できない。アルゴリズムが無限に実行される場合、そのフローは最大フローに近づいているかどうかも不明である。ただし、そのような状態はフローの値が無理数の場合でしか発生しない。容量が整数の場合、フォード・ファルカーソンの実行時間の上限は O(Ef) であり、E はグラフ内の枝数、f はグラフの最大フローである。これは、増加道が O(E) 回まで見つけることができ、毎回少なくともフローが 1 増加するためである。
フォード・ファルカーソンのアルゴリズムの派生として、エドモンズ-カープアルゴリズムがある。これは、終了することが保証されており、最大フローと実行時間が独立で、実行時間は O(VE) となる。
u {\displaystyle u} から v {\displaystyle v} へのフローが a {\displaystyle a} 、 v {\displaystyle v} から u {\displaystyle u} へのフローが b {\displaystyle b} であるとき、 f ( u , v ) = a − b {\displaystyle f(u,v)=a-b} であり、かつ f ( v , u ) = b − a {\displaystyle f(v,u)=b-a} となる。
∑ v f ( u , v ) = 0 ⟺ f i n ( u ) = f o u t ( u ) {\displaystyle \ \sum _{v}f(u,v)=0\Longleftrightarrow f_{in}(u)=f_{out}(u)} : s {\displaystyle s} と t {\displaystyle t} を除く全てのノード u {\displaystyle u} で成り立つ。あるノードに流れ込むフローとそこから出て行くフローは常に等しい。
すなわち、ネットワーク上のフローは、アルゴリズムの毎回の適用後に常に正当なものとなる。ここで、残余ネットワーク G f ( V , E f ) {\displaystyle G_{f}(V,E_{f})} を容量が c f ( u , v ) = c ( u , v ) − f ( u , v ) {\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)} で、フローのないネットワークと定義する。
ただし、 u , v {\displaystyle u,v} のフローによって u , v {\displaystyle u,v} がクローズ(満杯)となっても v , u {\displaystyle v,u} は残余ネットワークに残る可能性があるため、 E = E f {\displaystyle E=E_{f}} となるかどうかは定かではない。
アルゴリズム フォード・ファルカーソン
入力 フロー容量 c {\displaystyle \,c} 、始点 s {\displaystyle \,s} 、終点 t {\displaystyle \,t} のグラフ G {\displaystyle \,G}
出力 s {\displaystyle \,s} から t {\displaystyle \,t} へのフロー f {\displaystyle \,f} の最大値 全ての枝 ( u , v ) {\displaystyle \,(u,v)} について f ( u , v ) ← 0 {\displaystyle f(u,v)\leftarrow 0} とする。