フォード・ファルカーソンのアルゴリズム
ウィキペディア フリーな encyclopedia
フォード・ファルカーソンのアルゴリズム(英: Ford-Fulkerson algorithm)とは、フローネットワークにおける最大フローを求めるアルゴリズムである[1]。レスター・フォード Jr.(英語版、ドイツ語版、フランス語版、ロシア語版) と デルバート・ファルカーソン(英語版、ドイツ語版、スペイン語版、フランス語版) にちなんで命名されたもので、1956年に発表された。フォード・ファルカーソンのアルゴリズムの特殊版であるエドモンズ-カープアルゴリズムも「フォード・ファルカーソン」と呼ばれることがある。
このアルゴリズムの背景にある考え方は非常に単純である。始点から終点への経路があって、経路上の各辺に容量の空きがあるとき、その経路を使って流れを作ることができる。これを経路が見つかるたびにくりかえす。容量に空きがある経路を「増加道; augmenting path」と呼ぶ。