Dijkstra가 음의 모서리입니다. CLRS 의사 코드에 따라 작동하는 예제를 이해하지 못함

Question

EDIT 2 :이것은 CLRS에서 발생하지 않은 것처럼 보입니다. (CLRS 코드와 동일한 형식을 사용했기 때문입니다. Algos 및 DS 과정). 이 과정에서 우리는이 코드를 "Dijkstra 's Algorithm"인으로 지정했습니다.

나는 Why doesn't Dijkstra's algorithm work for negative weight edges?과 Negative weights using Dijkstra's Algorithm을 읽었습니다 (두 번째 것은 OP의 알고리즘과 관련이 있습니다).

CLRS의 의사 코드 (Intro to Algorithms)를 보면 Dijkstra가 음수 에지가있는 그래프의 예제에서는 작동하지 않는 이유를 알 수 없습니다.

가상 코드 (아래)에서 Insert 노드는 힙에 새 거리가 이전 거리보다 짧으면 힙으로 되돌아갑니다. 따라서 거리가 최종적으로 올바른 거리로 업데이트됩니다. 예를 들어

:

여기서 제는 (A, C)를 1로 설정하고 정확한 거리 -2 업데이트 적이되도록한다.

그러나 CLRS의 의사 코드는 먼저 C와 B를 거리 1과 2의 힙에 놓는다 고 말합니다. 그 다음 우리는 C를 터뜨리고 나가는 가장자리를 보지 않습니다. 그런 다음 B를 터뜨리고 가장자리 (B, C)를보고 Dist[C] > Dist[B] + w(B,C)을보고 Dist[C]을 -2로 업데이트하고 C를 다시 힙에 놓고 나가는 가장자리는 보이지 않도록합니다. 잘 작동했습니다. 이 질문에 대한 첫 번째 대답에서, 예를 들어 같은

: Negative weights using Dijkstra's Algorithm

대답의 저자는 C까지의 거리가 있기 때문에, -200으로 업데이트하지만, 사실이 아니다이 의사에 따라되지 않습니다 주장 이해 우리가 0 : 우리는

(CLRS에서 의사)

Dijkstra(G(V, E, ω), s ∈ V) 
for v in V do 
    dist[v] ← ∞ 
    prev[v] ← nil 
end for 
dist[s] = 0 
H←{(s,0)} 
while H̸=∅ do 
    v ← DeleteMin(H) 
    for (v, w) ∈ E do 
     if dist[w] > dist[v] + ω(v, w) then 
      dist[w] ← dist[v] + ω(v, w) 
      prev[w] ← v 
      Insert((w, dist[w]), H) 
     end if 
    end for 
end while 

편집 C.

에 올바른 최단 거리를 힙에 다시 B를 넣고 계산하는 것노드가 힙에서 빠져 나오면 최단 거리가 발견되었습니다. 하지만 여전히 (CLRS에 따르면) 노드가 이전에 계산 된 것보다 짧은 거리 인 heap에 다시 놓이는 것처럼 보이므로 결국 알고리즘이 실행될 때 우리는 관계없이 정확한 최단 거리를 얻어야합니다.