带负边的 Dijkstra。不理解示例，它们根据 CLRS 伪代码工作

Question

编辑 2： 这似乎不是来自 CLRS（我认为这是因为它遵循提供给我们的相同格式的 CLRS 代码在这个算法和 DS 课程中）。不过，在本课程中，我们得到的代码是 "Dijkstra's Algorithm".

我读了 Why doesn't Dijkstra's algorithm work for negative weight edges? and Negative weights using Dijkstra's Algorithm（我认为第二个是特定于 OP 的算法）。

查看来自 CLRS ("Intro to Algorithms") 的伪代码，我不明白为什么 Dijkstra 不能处理那些具有负边的图示例。

在伪代码（下面）中，如果到它们的新距离比之前到它们的距离短，我们 Insert 节点回到堆上，所以在我看来，距离最终会被更新到正确的距离。

例如：

这里的声明是 (A,C) 将被设置为 1 并且永远不会更新为正确的距离 -2。

但是CLRS的伪代码说我们先把C和B放到Heap上，距离分别为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，但根据这个伪代码，这是不正确的，因为我们会将 B 放回堆上，然后计算正确的最短距离到C.

（来自 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

编辑：我知道我们假设一旦一个节点从堆中弹出，就找到了最短距离；但是，似乎（根据 CLRS）如果距离比之前计算的更短，我们确实将节点放回堆上，所以最后当算法完成时运行我们应该无论如何得到正确的最短距离。

Answer 1

该实现在技术上不是 Dijkstra 的算法，Dijkstra here 描述了它（找不到更好的 link）：他所说的集合 A 是节点其中最小路径是已知的。所以一旦你将一个节点添加到这个集合中，它就固定了。您知道它的最小路径，并且它不再参与算法的其余部分。还讲到转移节点，所以不能同时在两个集合中。

这符合维基百科的伪代码：

 1  function Dijkstra(Graph, source):
 2
 3      create vertex set Q
 4
 5      for each vertex v in Graph:             // Initialization
 6          dist[v] ← INFINITY                  // Unknown distance from source to v
 7          prev[v] ← UNDEFINED                 // Previous node in optimal path from source
 8          add v to Q                          // All nodes initially in Q (unvisited nodes)
 9
10      dist[source] ← 0                        // Distance from source to source
11      
12      while Q is not empty:
13          u ← vertex in Q with min dist[u]    // Node with the least distance will be selected first
14          remove u from Q 
15          
16          for each neighbor v of u:           // where v is still in Q.
17              alt ← dist[u] + length(u, v)
18              if alt < dist[v]:               // A shorter path to v has been found
19                  dist[v] ← alt 
20                  prev[v] ← u 
21
22      return dist[], prev[]

还有它的堆伪代码。

但是，请注意维基百科在回答时还指出：

Instead of filling the priority queue with all nodes in the initialization phase, it is also possible to initialize it to contain only source; then, inside the if alt < dist[v] block, the node must be inserted if not already in the queue (instead of performing a decrease_priority operation).[3]:198

这样做仍然会导致在某些情况下重新插入具有负值边的节点，例如 second linked question.

的已接受答案中给出的示例图

所以好像有些作者把这个搞混了。在这种情况下，他们应该清楚地说明该实现要么适用于负边缘，要么不是正确的 Dijkstra 实现。

我想原始论文可能被解释得有点含糊。 Dijkstra 在其中没有任何地方提到负边或正边，也没有在任何替代解释之外明确说明节点不能在 A 集中更新一次。不知道是他自己在后续的作品或演讲中进一步澄清，还是其他人的解读。

所以从我的角度来看，你可以说它也是一个有效的 Dijkstra's。

至于为什么你可以这样实现它：因为如果我们只有积极的边缘，它在实践中可能不会慢，并且因为它可以更快地编写而无需执行额外的检查或不那么标准堆操作。

带负边的 Dijkstra。不理解示例，它们根据 CLRS 伪代码工作

Dijkstra with negative edges. Don't understand the examples, they work according to CLRS pseudocode

algorithm

computer-science

graph

dijkstra