私は無向グラフを持っています。私は、2つの与えられた頂点を分離する最小限のカットを見つけ出すように問題を減らすために、セットアップを変更することができます。私は重みが正で分数であると付け加えたい。無向グラフの入力として与えられた2つの任意の頂点間の最小カット
Stoer-Wagnerアルゴリズムは、指定されたノードをカットの異なる面に置くことを除いてすべてを行います.SWを修正する方法があれば、私は興味があります。
ありがとうございます。
Stoer-Wagnerについてはわかりませんが、この問題を解決する別の方法はMaxFlowです。
ノードの1つのセットをソースにリンクし、もう1つのノードを無限の容量でリンク先にリンクします。他のすべてのエッジは1のウェイトを持つ必要があります。次に、結果のグラフでMaxFlowを実行します。
終了したら、残りのネットワークのソースから引き続きアクセス可能なすべてのノード（最後のパス検出実行時にアクセスしたノード）をマークします。元のグラフのマークされたノードとマークされていないノードの間にあるエッジは、最小カットの一部です。
はい最大フローアルゴリズムは機能するかもしれませんが、正の分数ウェイトのエッジがあります。それは私ができない1です。メジャーな制約以外にも、これは私が必要とするものです。 – user2844647
@ user2844647この場合でもmax flowを実行することができます。最大容量のものを見つけるために経路探索アルゴリズムを変更し、追加された容量があるイプシロン（例えば、1e-3）未満のときに停止する。 – Sorin
2つのセットをメタノードに縮小します。 –
+ニコあなたは精巧にできますか？ – user2844647
それは基本的に彼の答えでSorinが説明したのと同様のアプローチです。しかし、2つのセットの頂点を新しいソースノードとシンクノードにリンクする代わりに、それらを置き換えてしまいました。 Btwでは、ウェイトは1に制限されていません。他のウェイト設定でソリンのアプローチを使用することができます。 –