为什么Dijkstra的算法不适用于负负边缘？

Question

有人可以告诉我为什么Dijkstra的单源最短路径算法假设边必须为非负。

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

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

编辑 更深入的解释：

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

它的想法是：如果我们有一个开放的顶点，使得它的成本最小-通过向任何顶点添加任何 正数 -最小值将永远不会改变。
如果没有对正数的限制-上述假设是不正确的。

由于我们“知道”每个“闭合”的顶点都是最小的-我们可以安全地执行松弛步骤-而无需“回头”。如果确实需要“回头看”，Bellman-
Ford会
提供类似递归（DP）的解决方案。