重み付けされた無向グラフのすべてのエッジの最短の代替パスを見つける必要があります。つまり、グラフにエッジ (a,b) があるとします。次に、直接をスキップして vetices a と b の間の最短のパスを計算したいと思います。パス、つまり edge(a,b) 。代替パスがない場合、距離は無限になります。グラフのすべてのエッジに対してこれを行う必要がありました.dijkstrasアルゴリズム(ターゲット頂点が検出されると壊れます)で試しましたが、特に代替手段がない場合、エッジごとにパスを個別に計算するには時間がかかりすぎますパスが可能です (その場合、グラフ全体をトラバースする必要があります)。これに対する他の代替ソリューションを提案できますか。
4 に答える
1
私がすることは、ダイクストラのアルゴリズムを適応させて、そのエッジを使用しない長さ 2 のすべてのパスを最初にヒープ/優先度キューに入力することだと思います (以前の間違いを見つけてくれた titus に感謝します)。そうすれば、得られる結果から、エッジを 1 つだけ含むパスが除外されます。その結果、特定の 1 つのソースのすべてが取得され、考えられるすべてのソースに対してこれを繰り返すことができます。
于 2012-08-09T17:40:11.053 に答える
-1
ダイクストラ法を実行する前に、グラフからターゲットエッジを削除するだけです。
于 2012-12-26T04:39:58.037 に答える
-1
これは私が少し前に書いたダイクストラの実装です。これはstlmake_heapを使用して、次のノードをより効率的に検索します。実装はおそらく正しいです。
編集：ファイルから読み取る場合の例でnは、は頂点の数、mはエッジの数a、bはエッジの頂点であり、方向はfromaからb、cは重みです。誰も
言及していない
ように、アルゴリズムをそのまま維持するには、エッジを削除してから追加し直す必要があります。
于 2012-08-09T17:27:25.217 に答える
-1
によって提案された解決策Dennis Mengは、私が考えるものです。ただし、実装を高速化できるいくつかの最適化 (前処理) があります。
グラフを一連の連結成分 (ツリー) に分離します [ヒント: DFS を使用して連結成分を見つけます]。
tree-- このようにして、 having ノードでペア (u,v) の最短パスが見つからない場合u、(内部) ループから抜け出すことができます。各ノードとそれに対応するツリーとの間のマッピングを維持します。-- これはステップ 1 の実装に役立ちます
于 2012-08-09T21:43:46.457 に答える