問題タブ [ford-fulkerson]

グラフに ford-fulkerson 法を適用して最大フローを見つける方法について、順を追って説明しているサイトを教えてください。

よろしくお願いします。

Ford–Fulkersonアルゴリズムを使用して、グラフの最大流量問題を解決しようとしています。アルゴリズムは、有向グラフでのみ説明されています。グラフが無向の場合はどうですか？

無向グラフを模倣するために私が行ったことは、頂点のペアの間に2つの有向エッジを使用することです。私を混乱させるのは、これらのエッジのそれぞれに残余エッジがあるべきか、それとも「反対」の方向付けられたエッジが残余エッジであるかということです。

私は最後のものを想定しましたが、私のアルゴリズムは無限ループに入っているようです。誰かが私に助けを与えてくれることを願っています。以下は私自身の実装です。検索でDFSを使用しています。

Cormen の「Introduction to algorithms 2nd Edition」から Ford-Fulkerson アルゴリズムを勉強しています。これは、有向グラフ G=(V, E) の擬似コードで次のように記述されます。ここで、f は VxV で定義されたフローです。

残差グラフ Gf は G と同じ頂点を持ち、c(u, v) - f(u, v) > 0 である順序付けられた頂点のペア (u, v) をエッジとして持ちます (編集: c は容量関数です)。開始時に与えられ、グラフの一部ではないエッジでゼロになるように拡張されます)

「両方向」にエッジが存在する場合、たとえばエッジとその逆がグラフにある場合にアルゴリズムで何が起こるかはわかりません。最小値の c(u, v) は、グラフの元の容量に対するものであると想定しています。(a, b) と (b, a) の両方がエッジである場合、残差グラフの 4 つのエッジを処理する必要がありますか? 現時点では、平行エッジを直接処理することはできません。

SO に関する次の質問を見つけました: 最大フロー - フォード ファルカーソン: 無向グラフ しかし、結果がどうなるかはわかりません。

Ford Fulkerson Algorithm を C++ で実装しようとしています。

しかし、私は自分のfind_edge機能に問題があります。でこの関数を呼び出すとmy_alg、正しいエッジが選択され、フローがインクリメントされmy_algます。右端を選択し、そのフローをインクリメントします ( flow) が、find_edge関数を再度呼び出すと、フローがインクリメントされません。

これにより、アルゴリズムの無限ループが発生します。おそらく私はポインターに何か問題があります。以下の私のコードを見ることができます。

cout ステートメントで「abc」を出力することすらありません。Ford-Fulkerson アルゴリズムを実装しようとしています。ここでは、ファイルから読み取り、容量フロー マトリックスを初期化しています。その後、ここでは省略した maxflow 関数を呼び出しています。

私はbfsを使用して拡張パスを見つけていますが、毎回同じパスを生成しています.しかし、フォードフルカーソンアルゴリズムでは、ソースからシンクへの毎回異なるパスを選択する必要があります. source と sink.graph の間の毎回のパスが指示され、重み付けされます

へのエッジを許可しないように残差ネットワークを再定義するとしsます。手順 FORD-FULKERSON が依然として最大フローを正しく計算していることを主張してください。

パスを拡張すると、リバース エッジの残りの容量が増加し、必要に応じてそのエッジのフローを減らすために使用できる (ただし、ネットワーク フローは全体的に増加する) と考えていました。したがって、エッジを許可しない場合は、エッジsのフローの減少を許可しないことを意味しますs- x(xは に隣接するノードsです)。したがって、エッジを許可すると、次sのようなサイクルを持つことができます

s to x_1 leadsto y leadsto x_2 to s to x_3 leadsto t

しかし、再びエッジを許可しないsと、サイクルなしで同じパスを見つけることができます。上記はすべて直感的なアイデアですが、正式な証明が必要です。

質問は、Cormen らによるアルゴリズム入門からのものです。

I've thus far been working with graphs whose vertices have only one directed edge between them. For all the examples I've used to test my implementation, the right answer has been produced. When I use a graph containing vertices which have an edge running both directions, however, I don't produce the right answer. I've been treating such an edge running backward as the backflow between those two vertices, as it seems that the backflow and a different "pipe" running backward would end up being equivalent. Is my assumption here wrong?

Ford Fulkerson アルゴリズムを Java で実装しようとしています。これまでのところ、ノードとエッジを含むグラフがあります。ノードには、ID 文字列とエッジの adjacencyList が含まれています。エッジには、容量とそれが導くノードが含まれます。

ウィキペディアのページにある疑似コードとその実装方法を理解しようとしています (私は Java を使用しています)。これは私がこれまでに理解していることです：

1. 最初に、グラフ内のすべてのエッジの流れをゼロに設定します。

2. 2 番目のステップは、エッジが残余容量を持つネットワークである残差グラフを作成することです: 容量 - フロー (「通常のグラフ」の対応するエッジの)。次に、この残差グラフを使用してソースからシンクへのパスを見つけ、このパスに沿って最小容量を見つけます。(これは本当にトリッキーになるところです。残差グラフ用にまったく新しいグラフを作成する必要がありますか、それとも元のグラフで何らかの方法で表現する必要がありますか?最善の方法は何ですか?)

ステップ 2 はパスが見つからなくなるまで繰り返されますが、パスが見つかるたびにステップ 3 と 4 を実行します。

1. パスに沿ったエッジごとに、ステップ 2 で見つけた最小値を追加します。

2. パスの反対方向のエッジごとに、ステップ 2 で見つけた最小値を引きます。

ステップ 3 と 4 は私を困惑させます。なぜなら、一方の方向に加算することと、反対方向に減算することは同じことだと思うからです。これらの加算と減算は、残差グラフではなく、グラフで行われますか?

助けていただければ幸いです。数時間この問題に頭を悩ませようとしていますが、理解できないようです。