Отрицательные веса с использованием алгоритма Дейкстры

Я пытаюсь понять, почему алгоритм Дейкстры не работает с отрицательными весами. Читая пример на Кратчайшие пути , я пытаюсь понять следующий сценарий:

    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.

Я не могу понять, почему при использовании следующей реализации Дейкстры 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)
}

Спасибо,

Меир

]