Próbuję zrozumieć, dlaczego algorytm Dijkstry nie będzie działał z ujemnymi wagami. Czytając przykład na Shortest Paths , próbuję rozgryźć następujący scenariusz:
2
A-------B
\ /
3 \ / -2
\ /
C
Ze strony internetowej:
Zakładając, że wszystkie krawędzie są skierowane od lewej do prawej, jeśli zaczniemy od A, algorytm Dijkstry wybierze krawędź (A, x) minimalizując d (A, A) + długość (krawędź), czyli (A, B). Następnie ustawia d (A, B) = 2 i wybiera inną krawędź (y, C) minimalizując d (A, y) + d (y, C); jedynym wyborem jest (A, C) i ustala d (A, C) = 3. Ale nigdy nie znajduje najkrótszej ścieżki z A do B, przez C, o łącznej długości 1.
Nie mogę zrozumieć, dlaczego przy użyciu następującej implementacji Dijkstry, d [B] nie zostanie zaktualizowany do 1(Kiedy algorytm osiągnie wierzchołek C, uruchomi relaksację na B, zobacz, że d [B] jest równe 2, a zatem zaktualizuje jego wartość do 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)
}
Dzięki,
Meir
