問題タブ [edmonds-karp]

ネットワーク フローがあり、Edmond-Karp アルゴリズムを使用すると、ネットワーク上にすでに最大フローがあるとします。では、任意のエッジ (一定の容量を持つ) をネットワークに追加した場合、最大フローを更新する最良の方法は何ですか? 新しいエッジに関する残差ネットワークを更新し、新しい最大フローが見つかるまで再び拡張パスを探すことを考えていましたが、それが機能するかどうか、またはそれが最善の方法であるかどうかはわかりません!

任意の拡張パスではなく、毎回最短の拡張パスを選択すると、Edmond Karps アルゴリズムが Ford-Fulkerson よりも高速になる理由

Boost-graph ライブラリのアルゴリズムで、バンドルされたプロパティで名前付きパラメータを使用しようとしています。edmonds_karp_max_flow

私の問題を示すために、既存のedmonds-karp の例を取り上げ、Internal プロパティを Bundled プロパティ (私は my properties edge_tand と呼びますnode_t) に変更し、Named パラメータを Non-named パラメータに変更しました。

正常にコンパイルされる名前のないパラメーターのバージョンは次のとおりです。

これは、コンパイルされず、多くのテンプレート エラーをトリガーする名前付きパラメーター バージョンです。

完全なedmonds-karp-eg_modified.cppソース:

返されるエラーは次のとおりです: http://pastebin.com/Vra8ZWHG。

名前のないパラメーターでは正常に機能します...しかし、名前付きパラメーターでは機能しません。

更新:誰かがまったく同じ問題を抱えているようです: svn.boost.org/trac/boost/ticket/8791。Boost 1.50彼は代わりにを使用して修正しました1.55。

• ブーストグラフのバージョン: 1.58.0
• コンパイラ: g++ 5.0

Ford-Fulkersons アルゴリズムを Java で実装する方法を学ぼうとしていて、インターネットでヘルプを見つけましたが、このコード スニペットで行き詰まってしまいました

コメントのおかげでそれがどのように機能するかはある程度理解できますが、なぜそれが必要なのか完全にはわかりません。なんで引き算する必要があるの？

ソース: http://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/

Edmonds-Karp アルゴリズムが経路 p に沿ってフロー f を増加させると言うとき、実際にフローを増加させるとはどういう意味ですか? パスに沿ってフローを送信することを意味しますか?

では、2 つの最短の増補経路の長さが 2 の場合、2 次フィルターは何になるでしょうか?

私が理解していることから、Edmonds-Karp は最短経路、つまりエッジの量が最も少ない経路を選択します。

ただし、これらのパスは両方とも長さ 2 です。したがって、このアルゴリズムは拡張され、「最大/最小フローでパスを選択する」と言いますか?

フローを最大化するために、C++ でEdmonds-Karpを実装しようとしていましたが、少し違った方法で記述しました。

1. 残差グラフのすべてのエッジを調べる代わりに、隣接リストを使用して、元のグラフに存在するエッジのみを調べました。
2. 残差グラフを最小フローで更新するときに、バックエッジを更新しませんでした。

興味深いことに、コードを実行すると、正しい結果が得られました。そこで、ウィキペディアの例に行きました。ここでは、バックエッジがどのように使用されているかを具体的に示しています。このグラフをコードに入力すると、再び正しい答えが得られました。結果のフロー マトリックスも確認しましたが、ウィキペディアのものと同じでした。

back-edge を追加および更新する必要がある理由を誰かが説明し、それらが重要な例を挙げてもらえますか?

これが私が書いたコードです（バックエッジを含めるように更新されています）：

Edmond-Karp のアルゴリズムを使用して解決することを決定した、マッチング問題から最大フロー問題への縮約を使用して、マッチング問題を解くプログラムを実装しています。

Edmond-Karp のアルゴリズムを使用して最大フロー問題を解決する手順を実行する方法を示すさまざまな疑似コードを調べて印象を取りました。これらの印象を組み合わせることで、多くの小さな基本グラフで機能する実装を作成しました。 . しかし、何らかの理由で、100 個のエッジを持つ 50 個のノード、またはそのようなグラフよりも大きなグラフなど、より大きなグラフに対して実装が間違った答えを返します。そのため、入出力シナリオの例を示しても、問題全体を強調するのにはあまり役立ちません (ただし、必要に応じて、そのような入出力シナリオを投稿できます)。私が「間違った答え」と言うとき、実装は実際には、解決するグラフが与えられたときに最大の一致 (または最大のフロー値) を与えません。

以下に、私の実装で使用されているすべての関連クラス、つまり MaxFlowSolver クラスがあります (メソッド solveFlowProblem(...) は、Edmond-Karp のアルゴリズム全体を使用するメソッドです)。

MaxFlowSolver

グラフ

角

私は主に、隣接ノードを使用した Edmond-Karp のアルゴリズムに関するウィキペディアの説明に従いましたが、他の情報源からも少しは参考にしましたが、それほど多くはありませんでした。ウィキペディアのアルゴリズムへのリンクは以下のとおりです。

https://en.wikipedia.org/wiki/Edmonds –Karp_algorithm#Pseudocode

ウィキペディアの疑似コードを間違って解釈した実装のどこかにありますか、それとも私のJavaコードでより具体的なものですか? 特定のグラフのプログラムが特定のグラフの最大一致 (または最大フロー) を出力しないという問題の原因を突き止めることなく、ほぼ一日中このプログラムを使用してきました。

私があなたから得ることができるすべての助けは非常に高く評価されます.

よろしくお願いします！