フォード・ファルカーソンのアルゴリズム

フォード・ファルカーソンのアルゴリズム（英: Ford-Fulkerson algorithm）とは、フローネットワークにおける最大フローを求めるアルゴリズムである^[1]。レスター・フォード Jr.（英語版、ドイツ語版、フランス語版、ロシア語版） と デルバート・ファルカーソン（英語版、ドイツ語版、スペイン語版、フランス語版） にちなんで命名されたもので、1956年に発表された。フォード・ファルカーソンのアルゴリズムの特殊版であるエドモンズ-カープアルゴリズムも「フォード・ファルカーソン」と呼ばれることがある。

このアルゴリズムの背景にある考え方は非常に単純である。始点から終点への経路があって、経路上の各辺に容量の空きがあるとき、その経路を使って流れを作ることができる。これを経路が見つかるたびにくりかえす。容量に空きがある経路を「増加道; augmenting path」と呼ぶ。

アルゴリズム

グラフ ${\displaystyle G(V,E)}$ にて、${\displaystyle u}$ から ${\displaystyle v}$ への容量 ${\displaystyle c(u,v)}$ でフロー ${\displaystyle f(u,v)=0}$ とする。ここで、始点 ${\displaystyle s}$ から終点 ${\displaystyle t}$ への最大フローを求める。最終的に、次のような状態となる。

• ${\displaystyle \ f(u,v)\leq c(u,v)}$ : ${\displaystyle u}$ から ${\displaystyle v}$ へのフローは容量を超えない。
• ${\displaystyle \ f(u,v)=-f(v,u)}$ : ${\displaystyle u}$ と ${\displaystyle v}$ の間の総フローの性質。${\displaystyle u}$ から ${\displaystyle v}$ へのフローが ${\displaystyle a}$、${\displaystyle v}$ から ${\displaystyle u}$ へのフローが ${\displaystyle b}$ であるとき、${\displaystyle f(u,v)=a-b}$ であり、かつ ${\displaystyle f(v,u)=b-a}$ となる。
• ${\displaystyle \ \sum _{v}f(u,v)=0\Longleftrightarrow f_{in}(u)=f_{out}(u)}$ : ${\displaystyle s}$ と ${\displaystyle t}$ を除く全てのノード ${\displaystyle u}$ で成り立つ。あるノードに流れ込むフローとそこから出て行くフローは常に等しい。

すなわち、ネットワーク上のフローは、アルゴリズムの毎回の適用後に常に正当なものとなる。ここで、残余ネットワーク ${\displaystyle G_{f}(V,E_{f})}$ を容量が ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$ で、フローのないネットワークと定義する。ただし、${\displaystyle u,v}$ のフローによって ${\displaystyle u,v}$ がクローズ（満杯）となっても ${\displaystyle v,u}$ は残余ネットワークに残る可能性があるため、${\displaystyle E=E_{f}}$ となるかどうかは定かではない。

アルゴリズム フォード・ファルカーソン

入力 フロー容量 ${\displaystyle \,c}$、始点 ${\displaystyle \,s}$、終点 ${\displaystyle \,t}$ のグラフ ${\displaystyle \,G}$

出力 ${\displaystyle \,s}$ から ${\displaystyle \,t}$ へのフロー ${\displaystyle \,f}$ の最大値

1. 全ての枝 ${\displaystyle \,(u,v)}$ について ${\displaystyle f(u,v)\leftarrow 0}$ とする。
2. ${\displaystyle \,G_{f}}$ 内で ${\displaystyle \,s}$ から ${\displaystyle \,t}$ への経路 ${\displaystyle \,p}$ があり、経路上の全ての枝 ${\displaystyle (u,v)\in p}$ について ${\displaystyle \,c_{f}(u,v)>0}$ であるとき:
   1. ${\displaystyle \,c_{f}(p)=\min\{c_{f}(u,v)\;|\;(u,v)\in p\}}$ を求める。
   2. ${\displaystyle (u,v)\in p}$ であるような各枝について
      1. ${\displaystyle f(u,v)\leftarrow f(u,v)+c_{f}(p)}$ （この枝にそってフローを送る）
      2. ${\displaystyle f(v,u)\leftarrow f(v,u)-c_{f}(p)}$ （フローは後で返される）

経路は、${\displaystyle G_{f}(V,E_{f})}$ について、例えば幅優先探索や深さ優先探索を行うことで得られる。前者の場合を特にエドモンズ-カープアルゴリズムと呼ぶ。

複雑性

フロー増加道をグラフ上で既に確立されているフローに追加していくと、最終的にフロー増加道が見つからなくなり、最大フローが得られる。しかし、そのような状態に到達するかどうかは不確実であり、単にアルゴリズムが完了した場合は解が正しいということしか保証できない。アルゴリズムが無限に実行される場合、そのフローは最大フローに近づいているかどうかも不明である。ただし、そのような状態はフローの値が無理数の場合でしか発生しない。容量が整数の場合、フォード・ファルカーソンの実行時間の上限は O(Ef) であり、E はグラフ内の枝数、f はグラフの最大フローである。これは、増加道が O(E) 回まで見つけることができ、毎回少なくともフローが 1 増加するためである。

フォード・ファルカーソンのアルゴリズムの派生として、エドモンズ-カープアルゴリズムがある。これは、終了することが保証されており、最大フローと実行時間が独立で、実行時間は O(VE²) となる。

例

以下の例は、4ノードのフローネットワークでフォード・ファルカーソンのアルゴリズムを適用する様子を最初の数ステップだけ図示したものである。始点は A で終点は D。増加道は深さ優先探索で探し、隣接ノードは辞書順で調べる。この例では、アルゴリズムの最悪ケースを示している。各ステップではフローは1ずつしか増えない。この場合、幅優先探索で経路を求めると、2ステップで完了する。

経路	容量	フローネットワーク
	初期状態のフローネットワーク
${\displaystyle A,B,C,D}$	${\displaystyle \min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D))}$ ${\displaystyle =\min(c(A,B)-f(A,B),c(B,C)-f(B,C),c(C,D)-f(C,D))}$ ${\displaystyle =\min(1000-0,1-0,1000-0)}$ ${\displaystyle =1}$
${\displaystyle A,C,B,D}$	${\displaystyle \min(c_{f}(A,C),c_{f}(C,B),c_{f}(B,D))}$ ${\displaystyle =\min(c(A,C)-f(A,C),c(C,B)-f(C,B),c(B,D)-f(B,D))}$ ${\displaystyle =\min(1000-0,0-(-1),1000-0)}$ ${\displaystyle =1}$
	1998ステップ後…
	最終的なフローネットワーク

経路 A,C,B,D を見つけたとき、C から B へフローが押し戻される点に注意されたい。

参考文献

外部リンク

• Ford-Fulkerson's algorithm アニメーション解説あり

ウィキメディア・コモンズには、フォード・ファルカーソンのアルゴリズムに関するカテゴリがあります。

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形(無制約)	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 連続放物線補間（英語版） 勾配法 収束性 信頼領域 ウルフ条件（英語版） 準ニュートン法 BFGS法 ブロイデン法 L-BFGS（英語版） DFP法 対称ランク1法（英語版） その他の求解法 ガウス・ニュートン法 最急降下法 レーベンバーグ・マルカート法 共役勾配法（非線形共役勾配法） 切り捨てニュートン法（英語版） ドッグレッグ法 … ヘッセ行列 最適化におけるニュートン法（英語版）
非線形(制約付き)	一般 バリア関数 ペナルティ関数法（英語版） 微分可能 ラグランジュの未定乗数法 逐次二次計画法 連続線形計画（英語版）
凸最適化	凸縮小化 切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版） 簡約勾配法 劣勾配法（英語版） 線型 および 二次 内点法 カチヤン楕円体法 カーマーカーの投影アルゴリズム ベイズ-交換 単体法 改訂シンプレックス法（英語版） 十字法（英語版） レムケの主ピボット操作法（英語版）
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題(分枝限定法 若しくは 切断) グラフ理論 最小全域木 ベルマン–フォード法 ブルーフカ法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） クラスカル法 最大フロー問題 Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）
メタヒューリスティクス	進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）