Я пытаюсь понять, почему алгоритм Дейкстры не будет работать с отрицательными весами. Прочитав пример на Кратчайшие пути, я пытаюсь выяснить следующий сценарий:
2
A-------B
\ /
3 \ / -2
\ /
C
С веб-сайта:
Предполагая, что ребра направлены слева направо, если мы начнем с A, алгоритм Дейкстры выберет ребро (A, x), минимизирующее d (A, A) + длина (ребро), а именно (A, B). Затем он устанавливает d (A, B) = 2 и выбирает другое ребро (y, C), минимизирующее d (A, y) + d (y, C); единственным выбором является (A, C) и он устанавливает d (A, C) = 3. Но он никогда не находит кратчайший путь от А до B, через C, с общей длиной 1.
Я не могу понять, почему использование следующей реализации Dijkstra, 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)
}
Спасибо,
Меир
