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

ウィキペディア

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/04/10 17:31 UTC 版)

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "フォード・ファルカーソンのアルゴリズム" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2015年11月)

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

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

アルゴリズム

グラフ ${\displaystyle G(V,E)}$ ${\displaystyle A,B,C,D}$ ${\displaystyle A,C,B,D}$ 1998ステップ後… 最終的なフローネットワーク

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

参考文献

1. ^ T. コルメン、R. リベスト、C. シュタイン、C. ライザーソン『アルゴリズムイントロダクション』（第3版）近代科学社、2013年12月17日（原著2009-7-31）。ISBN 476490408X。 

外部リンク

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

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

表 話 編 歴 アルゴリズム
ソート	比較ソート バブルソート 選択ソート 挿入ソート シェルソート クイックソート マージソート ヒープソート シェーカーソート コムソート ノームソート 図書館ソート イントロソート 奇偶転置ソート 線形時間ソート 鳩の巣ソート 基数ソート バケットソート 並行ソート ソーティングネットワーク バッチャー奇偶マージソート シェアソート 非効率的 ボゴソート ストゥージソート グラフ トポロジカルソート
探索	リスト 線形探索 二分探索 木・グラフ 幅優先探索 最良優先探索 均一コスト探索 A* 深さ優先探索 反復深化深さ優先探索 深さ制限探索 双方向探索 分枝限定法 ビームサーチ 文字列 クヌース–モリス–プラット法 ボイヤー-ムーア法 エイホ–コラシック法 ラビン-カープ法 Bitap法
最短経路問題	ダイクストラ法 ベルマン–フォード法 ワーシャル–フロイド法
最小全域木	プリム法 クラスカル法
最大フロー問題 最小カット問題	フォード・ファルカーソン法 エドモンズ・カープ法
線型計画問題	シンプレックス法 カーマーカー法
順序統計量	選択アルゴリズム クイックセレクト 中央値の中央値
計算幾何学	凸包アルゴリズム
種類	近似アルゴリズム 乱択アルゴリズム 並列アルゴリズム 分散アルゴリズム 可積分アルゴリズム
その他	分割統治法 動的計画法 貪欲法 アルゴリズム作曲法
カテゴリ

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