小编典典

为什么 Dijkstra 的算法不适用于负权重边缘?

all

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

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


阅读 166

收藏
2022-08-05

共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) 的解决方案。

2022-08-05