Ford-Fulkersonアルゴリズムは、1950年代にEdward F. Mooreにより考案され、後の1962年にLester R. Ford Jr.とDelbert R. Fulkersonによって改良・公式化された。最大流量問題の解法としての重要性を背景に、現在もネットワークフロー理論において広く採用されている。
この記事の目次
- Ford-Fulkersonアルゴリズムの定義
- Ford-Fulkersonアルゴリズムの仕組み
- Ford-Fulkersonアルゴリズムの歴史
- Ford-Fulkerson対エッカート-カープ
- まとめ
Ford-Fulkersonアルゴリズムの定義
Ford-Fulkersonアルゴリズムは、有向グラフにおける最大流量問題を解くための手法です。これは始点から終点へのパスを見つけ出し、そのパスを通じて可能な限り多くの流動量を送るという過程を繰り返すことで成り立っています。
この方法では、既に流れている流量とネットワークの容量との差である余裕容量が重要な役割を果たします。最大流量に達するまで、どのパスでも余裕容量がある限り流動量は増加可能です。
Ford-Fulkersonアルゴリズムの仕組み
このアルゴリズムはまずネットワークグラフを定義します。ここで、各エッジには最大流量と既存の流量が設定されます。
その後、始点から終点への経路を探し、その経路上の最小余裕容量を見つけます。これを最大流増加量として用います。
Ford-Fulkersonアルゴリズムの歴史
Ford-Fulkersonアルゴリズムの基礎となる概念は、1950年代にEdward F. Mooreにより提案されました。これは最大流量問題へのアプローチとして初めて示されたものです。
その後、このアイデアはLester R. Ford Jr.とDelbert R. Fulkersonによって引き継がれ、さらに詳細化・改善され、1962年に正式なアルゴリズムとして発表されました。
Ford-Fulkerson対エッカート-カープ
Ford-FulkersonとEdmonds-Karpアルゴリズムは、どちらも最大流量問題の解法として使用されます。ただし、両者の基本方針は異なります。
Ford-Fulkersonでは、増大経路の選択は任意に行われますが、これは効率性を損なう可能性があります。一方でEdmonds-Karpアルゴリズムは最短パス優先を選択し、これによりより速やかな結果を得ることができます。
まとめ
Ford-Fulkersonは最大流量問題を解決する基本的なアプローチであり、その後の多くのネットワークフロー理論への発展に重要な影響を与えている
※本記事はIT用語辞典の手書きドラフトです。公開前に最新情報・出典を確認のうえ加筆修正してください。
コメント