0

次のグラフで A から B への 2 つのパスを計算する必要がありますが、パスがエッジを共有できないという制約があります。

うーん、わかりました。画像を投稿できません。ここにリンクがあります。

すべてのエッジには正の重みがあります。この例では、それらが等しいと仮定できると思います。私の素朴なアプローチは、上の画像の 2 番目のグラフに示されているように、Djikstra のアルゴリズムを使用して最初のパスを計算することです。

次に、グラフからエッジを削除し、2 番目のパスを計算しようとしましたが、失敗しました。上記の 3 番目の図に示されているパスを計算する Djikstra、Bellman-Ford (またはその他のもの) のバリエーションはありますか? (特別な知識やサブテンド リンクの削除なしで、という意味です)

4

1 に答える 1

0

あなたが探しているのは、エッジのないパスです。メンガーの定理は、エッジ分離パスの最大数を提供します。最短のペアを見つけるには、Edge disjoint shortest pair アルゴリズムを見てください。

  1. 指定された頂点のペアに対して最短ペア アルゴリズムを実行します。
  2. 最短パスの各エッジ (2 つの反対方向のアークに相当) を、ソース頂点に向かう単一のアークに置き換えます。
  3. 上記の各円弧の長さを負にします
  4. 最短経路アルゴリズムを実行します (注: アルゴリズムは負のコストを受け入れる必要があります)。
  5. 見つかった 2 つのパスの重なっているエッジを消去し、最初の最短パス上の残りのアークの方向を逆にして、その上の各アークがシンク頂点に向けられるようにします。目的のパスのペアが得られます。
于 2010-05-12T17:52:44.090 に答える