問題タブ [edmonds-karp]

Edmonds–Karpアルゴリズムのwikiページで見つけた擬似コードを使用してEdmonds–Karpアルゴリズムを実装しました：http：//en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm

それはうまく機能しますが、アルゴリズムの出力は最大フロー値（最小カット値）です。このカットに含まれるエッジのリストを作成する必要があります

アルゴリズムを変更しようとしましたが、成功しませんでした。

ありがとうございました

すべてのパスが同じ長さである場合、 Edmonds-Karpアルゴリズムの開始パスを選択するにはどうすればよいですか？この場合、最大フローはパスシーケンスの決定に従って変化します。

このアルゴリズムを有向グラフに実装しています。しかし、このグラフノードの興味深い点には、独自のフロー容量もあります。元の問題のこの微妙な変更は、特別な方法で処理する必要があると思います。なぜなら、元の最大フロー問題では、最初から最後まで任意のパスを見つけることができました（実際、エドモンズ・カープアルゴリズムでは、BFSを実行し、最後のノードに到達する最初のパスを選択する必要があります）しかし、このノードでは-容量の拡張については、「このパスの選択」ジョブについてさらに注意する必要があります。私は元のアルゴリズムを実装し、max-flowよりも小さいフロー値を取得していることに気付いたので、それがこのノード容量の制限に関係しているとは思えないので、私はそれを知っています。

私はこれに多大な努力を払い、自己ループを追加することによって（各ノードに自己ループを追加し、それぞれのこの自己ループを含むパスを見つけることによって、ノードに容量の制約がないグラフに初期グラフを変換するなどのいくつかのアイデアを思いつきましたパス上のノード）または初期のノード容量の制約に優先する重みを持つ仮想ノードとエッジを追加する）ただし、これらのいずれかがこの問題の優れた解決策であるとは確信していません。

どんなアイデアでも大歓迎です。

前もって感謝します。

Edmond Karp アルゴリズムを実装しますが、それは正しくないようで、正しいフローが得られません。次のグラフと 4 から 8 までのフローを検討してください。

アルゴリズムは次のように実行されます。

最初に 4→1→8 を見つけ、次に 4→5→8 を見つけ、その後 4→1→6→8 を見つけます

そして、3 番目のパスは間違っていると思います。このパスを使用すると、6 → 8 のフローが使用できず (使用されているため)、実際には 4 → 5 → 6 → 8 のフローが使用できないからです。

実際、4→5→6→8、次に 4→1→3→7→8、次に 4→1→3→7→8 を選択すると、より良いフローを得ることができます(40)。

ウィキのサンプルコードからアルゴリズムを実装しました。有効なパスは使用できないと思います。実際、この貪欲な選択は間違っています。

私が間違っている？

コードは次のとおりです (c# では、しきい値は 0 で、アルゴリズムには影響しません)。

使用可能な容量が 0 と 1 のみの場合、エドモンズ カープ (BFS) の上限はいくつですか?

容量が 0 と 1 の場合の違いがわかりません。Ford Fulkerson が、容量が 0 と 1 の場合、フロー値が 0 または 1 であることを発見したことを知っています。これは役に立ちますか?

質問に飛び込む前に、私がすでに持っているものの背景情報をいくつか示します。

-最初に、エッジの重みが計算された距離である米国中の都市に基づいて、無向隣接行列グラフを作成しました (距離式によって達成されました)。

-Prim のアルゴリズムを使用して、最小スパニング ツリーも実装しました。

今、私が持っている Edmonds Karp 最大フロー アルゴリズムを実装する必要がありますが、次のコードで使用されるアルゴリズムを実装するために、私が持っているデータに基づいて容量グラフを作成する方法について混乱しています:

どんな助けでも大歓迎です、ありがとう!

Ford-Fulkerson と Edmonds-Karp など。アル。ゼロフローから始めて、それ以上増やせなくなるまで増やします。正の容量の場合。ただし、最初のゼロ フローは、正当なフローであり、容量の制約を満たすフローであることが保証されています。

負の容量では、すべてゼロのフロー割り当ては容量の制約を満たさないため、最大フローに拡張できません。

インターネット上で、負の容量を持つ最大フローは 2 つの最大フローの問題として解決できると示唆しているのを読んだことがありますが、その方法を理解することはできませんでした...

私たちの多くは、コーメン教授らの「アルゴリズム入門」と同じ版を持っていないと思うので、以下に補題 (および私の質問) を書きます。

Edmonds-Karp アルゴリズム

補題 26.7 (第 3 版では、第 2 版では補題 26.8 になる場合があります): ソース s とシンク t をもつフロー ネットワーク G=(V,E) で Edmonds-Karp アルゴリズムを実行すると、V{ s,t}、残差ネットワーク Gf の最短経路距離 df(s,v) は、各フロー拡張で単調に増加します。

証明: まず、V{s,t} のある頂点 v に対して、s から v への最短経路距離を減少させるフロー拡張があると仮定すると、矛盾が導き出されます。最短経路距離を減少させる最初の拡張の直前のフローを f とし、直後のフローを f' とします。df'(s,v) < df(s,v) となるように、拡張によって距離が減少した最小 df'(s,v) を持つ頂点を v とする。p = s ~~> u -> u を Gf' における s から v への最短経路とし、Ef' における (u,v) および

df'(s,u) = df'(s,v) - 1. (26.12)

v をどのように選択したかにより、ソース s から頂点 u までの距離が減少していないことがわかります。

df'(s,u) >= df(s,u)。(26.13)

...

私の質問は次のとおりです。私はそのフレーズをよく理解していません

" v をどのように選択したかにより、ソース s から頂点 u までの距離が減少しないことがわかります。つまり、df'(s,u) >= df(s,u) (26.13) "

v の選択方法は、「s から頂点 u までの距離が減少しない」という性質にどのように影響しますか? 式 (26.13) を導き出すにはどうすればよいですか。

u はパス (s,v) 上の頂点であり、(u,v) も (s,v) の一部です。(s,u) も減らないのはなぜですか?

ご協力ありがとうございました。