問題定義

各エッジに対し、流量の最大値（容量、キャパシティ）が定められたグラフにおいて、単一の始点から単一の終点への流量の最大値（最大フロー）を求める。

解法

基本的な考え方

• 何でも良いので、始点から終点までをつなぐパス P を1つ見つける
  • ただし、キャパシティがゼロ（= 全く流れない）のエッジは使わない
• パス P に流すことができる最大まで流す
  • P を構成するエッジのうち、一番キャパシティが小さいところがボトルネック
• 流したエッジはその分だけキャパシティが減る
• 以上を、流せるパスが見つからなくなるまで繰り返す

処理の流れ

1. フロー変数 $f = 0$ とする
2. 各エッジと逆向きに、キャパシティがゼロのエッジを張る
3. グラフ上で、キャパシティがゼロでない（= まだ流す余地がある） エッジからなる始点〜終点のパス P を1つ見つける
   • パス P の各エッジのキャパシティのうち、最小のものを $C_{\rm min}$ とする
   • 見つからなかったら処理終了
4. パス P に対し、以下の処理を行う
   • パス P の各エッジのキャパシティを $C_{\rm min}$ だけ減らす
   • パス P の各エッジの逆エッジのキャパシティを $C_{\rm min}$ だけ増やす
   • $f$ を $C_{\rm min}$ だけ増やす
5. 3に戻る

【NOTE】逆向きエッジの役割

重要な特性として、逆向きエッジのキャパシティ初期値はすべてゼロなので、

• 最低一度は元のエッジにフローが流れないと、逆向きエッジには全くフローを流すことができない
• 逆向きエッジを流れることができるフローは、元のエッジを流れるフロー以上にはできない

逆エッジにフローを流すとき、その逆エッジ、すなわち元のエッジのキャパシティが増える。
これは、元のエッジを通るフローを減らすことに等しい。
つまり、それ以前のパス探索で流すと決めたフローをキャンセルしている。

具体例

例題として、以下の有向グラフにおける S → T の最大フロー問題を考える（エッジ上の数値はキャパシティを表す）。

キャパシティゼロの逆向きエッジを張る：

S → T のパスを1つ見つけ、流せるだけ流す（1回目）：

S → T のパスを1つ見つけ、流せるだけ流す（2回目）：

S → T のパスを1つ見つけ、流せるだけ流す（3回目）：

これ以上流せるパスがない：

結果、以下のように流すときに最大フロー6が実現できる（エッジ上の表記は 実際の流量/キャパシティ を表す）。

【NOTE】

この手法で求まる流れ方はあくまで解の1つであり、同じ最大フローを満たす別の流れ方は存在し得る。