为什么Dijkstra的算法对负权边不起作用？

Question

我说的只是边缘，而不是负权重循环。

Answer 1

回想一下，在Dijkstra的算法中，一旦一个顶点被标记为“闭合”（并且脱离了开集）--算法找到了通往它的最短路径，并且永远不必再开发这个节点--它假设开发到这个路径的路径是最短的。

但如果是负权重--这可能不是真的。例如：

       A
      / \
     /   \
    /     \
   5       2
  /         \
  B--(-10)-->C

V={A,B,C} ; E = {(A,C,2), (A,B,5), (B,C,-10)}

来自A的Dijkstra将首先开发C，随后将无法找到A->B->C

编辑一个稍微深一点的解释：

注意，这是很重要的，因为在每个松弛步骤中，算法假定“关闭”节点的“代价”确实是最小的，因此接下来将被选择的节点也是最小的。

它的思想是：如果我们有一个开放的顶点，使得它的代价是最小的--通过在任何顶点上添加任何正数--最小性永远不会改变。
没有对正数的约束--上述假设不成立。