algorithm - ダイクストラアルゴリズムについての混乱？

Question

Algorithms book Cormanによると、Dijkstra は、すべてのエッジの重みが負でないグラフにのみ適用されます。つまり、負の重みを持つエッジがある場合、グラフ全体で機能しないということですか? または負の重みエッジをカウントしませんか? どちらが正しいか教えてください。

score 7 · Accepted Answer

ダイクストラアルゴリズムは、次のようないくつかの負のエッジのグラフで機能することがあります。

A-->B-->C

w(A, B) = -1とw(B, C) = -2。_

しかし、少なくとも 1 つの負のエッジがある場合、それが常に正しいとは証明できません。お気に入り：

A-->B-->C-->D
 \         /
  \ _____ /

ここw(A, B) = 1でw(B, C) = 3、、、、。w(C, D) = -5_w(A, D) = 2

ソースポイントとして A を選択した場合、A から D までの最短経路の長さは、実際2ではなくダイクストラアルゴリズムによって取得されます。-1

これは、ダイクストラアルゴリズムが貪欲なアルゴリズムであり、正しさの証明手順がすべてのエッジが非負であることを使用して矛盾を取得するためです。その証明手順については、定理 24.6 (ダイクストラのアルゴリズムの正しさ) のアルゴリズム入門で調べることができます。

score 0 · Accepted Answer

負のエッジの主な問題は、負のサイクルです。グラフが頂点 S と頂点 T の間に負のサイクルを含む場合、S と T の間に最短経路はありません。ダイクストラは最短経路を見つけますが、これは正しくありません。

したがって、負のエッジは無視されるだけでなく、完全に誤った解に寄与します。

代替手段は、|V| 回目の反復でこれらの負のサイクルを見つける Bellman-Ford アルゴリズムです。

2 に答える 2