ダイクストラのアルゴリズムが負の重みで機能しない理由を理解しようとしています。最短経路の例を読んで、私は次のシナリオを理解しようとしています。
2
A-------B
\ /
3 \ / -2
\ /
C
ウェブサイトから：
エッジがすべて左から右に向けられていると仮定すると、Aから始める場合、ダイクストラのアルゴリズムは、d（A、A）+ length（edge）、つまり（A、B）を最小化するエッジ（A、x）を選択します。次に、d（A、B）= 2を設定し、d（A、y）+ d（y、C）を最小化する別のエッジ（y、C）を選択します。唯一の選択肢は（A、C）で、d（A、C）=3に設定されます。ただし、全長1で、Cを経由してAからBへの最短経路を見つけることはありません。
次のダイクストラの実装を使用すると、d [B]がに更新されない理由がわかりません1（アルゴリズムが頂点Cに到達すると、Bでリラックスが実行され、d [B]がに等しいことを確認して、2更新します）その値を1）に。
Dijkstra(G, w, s) {
Initialize-Single-Source(G, s)
S ← Ø
Q ← V[G]//priority queue by d[v]
while Q ≠ Ø do
u ← Extract-Min(Q)
S ← S U {u}
for each vertex v in Adj[u] do
Relax(u, v)
}
Initialize-Single-Source(G, s) {
for each vertex v V(G)
d[v] ← ∞
π[v] ← NIL
d[s] ← 0
}
Relax(u, v) {
//update only if we found a strictly shortest path
if d[v] > d[u] + w(u,v)
d[v] ← d[u] + w(u,v)
π[v] ← u
Update(Q, v)
}
ありがとう、
メイア
）。