algorithm - 最小コスト フローから最大フロー

Question

最小コスト フローの問題から最大フローの問題への削減はありますか? それともその逆？最小コスト フロー アルゴリズムを使用して、最大フローの問題を解決したいと考えています。

Answer 1

申し訳ありませんが、初めて質問を誤解したと思います。はい、最小コストは最大フローの特殊なケースです。最大フローではなく、最小コストは、各エッジを通過した後、フローにコストがあることを前提としています。したがって、各エッジのコストをゼロに設定すると、最小コストが最大フローまで削減されます。

編集：

最小コストの問題では、最初に送信する事前定義済みの必要なフローが必要です。c(u, v) = 0最大値を検索するには、上記のアルゴリズム (エッジのコストを使用) を複数回実行する必要があります。特定の範囲の値について、二分探索を使用して最大値をより効率的に見つけることができます。

Min Cut Max Flow のことですか？（編集：あなたがこれを意味しているとは思いませんが、これは最大フローを証明するための基礎であり、そうでない場合は一見の価値があります）グラフをドロップして自分で最小カットを行うと、理解しやすくなります。

Answer 2

各エッジに -1 のコスト (単位フローあたり) を追加してから、コスト最小化アルゴリズムを使用します。それが流れを最大化します。