並列エッジと自己ループを持つDijkstra

Question

負の重みを持たない重み付き無向グラフですが、頂点と自己ループの間に複数のエッジを含むことができる場合は、問題なしでDijkstraアルゴリズムを実行して、または目的地があるか、または反例が存在するか？

私の推測では、問題はないと確信しています。

Answer 1

Dijkstraのアルゴリズムをグラフに変更せずに実行する場合は、ではなく、がソースとデスティネーションの最短経路を取得する可能性があります。

たとえば、SとOを考えてみましょう。最短パスを見つけることは、Oをキューにプッシュしたいときに、どのエッジが横断されているかによって異なります。コードがウェイト1でエッジを選択した場合は、問題ありません。しかし、コードがウェイト8でエッジを選択すると、アルゴリズムが間違った答えを与えることになります。

これは、アルゴリズムの正確さが、送信元ノードの隣接リストに入力されたエッジの順序に依存するようになったことを意味します。

Answer 2

グラフは、シングルエッジループや平行エッジのないグラフに簡単に変換できます。

シングルエッジループの場合、重量が負であるかどうかを確認する必要があります。ウェイトが負の場合、明らかに最短パスはありません。スピンを維持し、パスの長さを制限を超えて減らすことができます。しかし、ウェイトが正の場合、そのエッジを通過できる最短経路がないので、そのエッジを投げることができます。

ゼロウェイトエッジは、ゼロウェイトループと同様の問題を引き起こします。同じループを何度も繰り返し実行する最短パスは無限にあります。このような場合には、もう一度グラフからエッジを取り除くことが賢明です。

平行なエッジのうち、最も軽いもの以外のものをすべて捨てることができます。この理由は同じように簡単です。最短パスがある場合は、Aのエッジが平行で、ウェイトが小さいBの場合は、AをBに置き換えるだけで、さらに短いパスを構築できます。したがって、最短経路はAになることはできません。

Answer 3

わずかな変更が必要です。そこからUVに向かう複数のエッジがあり、各エッジがどちらかでき、異なる重みを有する場合：

1. を緩和するための少なくともエッジに重みを選び、または
2. 各エッジの緩和を実行します。

＃2の定数にはより高い値がありますが、どちらも同じ複雑さを持ちます。あなたはUの次の隣接ノードに移動する前間のすべてのエッジのuとVを評価することを確認する必要がありますどのような場合には

。