php - 「重み付けされた」エッジを持つ Ford-Fulkerson アルゴリズム

Question

エッジに「重量」の余分な次元を追加するフォード・フルカーソンのバリエーションはありますか?

つまり、一部のエッジは他のエッジよりも理想的であり、すべての可能性がある一方で、理想的でないエッジよりも理想的なエッジを優先します。

score 3 · Accepted Answer

重みを追加するために私が知っている 2 つの一般的な一般化があります。

最小コストフロー

各エッジに重みがあり、制約を満たし、最小コストのフローを計算したいとします。(コスト = 重量の合計 * 関連するエッジに沿って流れる単位)

この問題は最小コストフローと呼ばれます。

実装は、 min-cost-flowと呼ばれる networkx にあります。

これは、主双対アプローチに関する優れたトップコーダーのチュートリアルです。

このための私のお気に入りのアルゴリズムは、実際には 1961 年に Fulkerson 自身によって発明されたもので、アウトオブキルターアルゴリズムと呼ばれています。

間違いなく最大のフローが必要であるが、重みが最小のフローを選択したいとします。

これは、min-cost-flow が最大の可能なフローを提供しない可能性があるという点で、最初の解釈とは異なります。たとえば、フローが 0 から 1 の範囲にあり、重みが 1 であるという制約を持つ単一のエッジ start->end があるとします。

min-cost-flow は 0 のフローになり、max-flow-min-cost は 1 のフローになります。

これの実装は、 max_flow_min_cost と呼ばれるnetworkxにあります。