125

我试图理解为什么 Dijkstra 的算法不适用于负权重。阅读有关Shortest Paths的示例，我试图找出以下情况：

    2
A-------B
 \     /
3 \   / -2
   \ /
    C

从网站：

假设边都是从左到右的，如果我们从 A 开始，Dijkstra 的算法会选择边 (A,x) 最小化 d(A,A)+length(edge)，即 (A,B)。然后它设置 d(A,B)=2 并选择另一个边 (y,C) 最小化 d(A,y)+d(y,C)；唯一的选择是 (A,C)，它设置 d(A,C)=3。但它永远不会找到从 A 到 B、通过 C、总长度为 1 的最短路径。

我不明白为什么使用 Dijkstra 的以下实现，d[B] 不会更新为1（当算法到达顶点 C 时，它将在 B 上运行松弛，看到 d[B] 等于2，因此更新其值为1)。

Dijkstra(G, w, s)  {
   Initialize-Single-Source(G, s)
   S ← Ø
   Q ← V[G]//priority queue by d[v]
   while Q ≠ Ø do
      u ← Extract-Min(Q)
      S ← S U {u}
      for each vertex v in Adj[u] do
         Relax(u, v)
}

Initialize-Single-Source(G, s) {
   for each vertex v  V(G)
      d[v] ← ∞
      π[v] ← NIL
   d[s] ← 0
}

Relax(u, v) {
   //update only if we found a strictly shortest path
   if d[v] > d[u] + w(u,v) 
      d[v] ← d[u] + w(u,v)
      π[v] ← u
      Update(Q, v)
}

谢谢，

梅尔

4

9 回答 9

222

您建议的算法确实会在该图中找到最短路径，但通常不是所有图。例如，考虑这个图表：

具有四个节点 A、B、C 和 D 的有向图。节点 A 到 B 的边的成本为 1，边到 C 的成本为 0，边到 D 的成本为 99。节点 B 的边到到节点 C 的成本为 1。节点 D 到节点 B 的成本为 -300。

让我们跟踪您的算法的执行情况。

  1. 首先，将 d( A ) 设置为 0，将其他距离设置为 ∞。
  2. 然后展开节点A，将 d( B ) 设置为 1，将 d( C ) 设置为 0，将 d( D ) 设置为 99。
  3. 接下来，展开C，没有净变化。
  4. 然后展开B，这没有任何效果。
  5. 最后，展开D，将 d( B ) 更改为 -201。

请注意，尽管到C的最短路径长度为 -200 ，但在此结束时，d( C ) 仍然为 0 。这意味着您的算法不会计算到所有节点的正确距离。此外，即使您要存储说明如何从每个节点到起始节点A的反向指针，您也会最终选择从C到A的错误路径。

原因是 Dijkstra 的算法（和您的算法）是贪心算法，它假设一旦计算了到某个节点的距离，找到的距离必须是最佳距离。换句话说，该算法不允许自己获取已扩展节点的距离并更改该距离。在负边缘的情况下，您的算法和 Dijkstra 的算法可能会因为看到负成本边缘而感到“惊讶”，这确实会降低从起始节点到其他节点的最佳路径的成本。

希望这可以帮助！

于 2011-07-23T08:53:12.013 回答
31

请注意，如果图形没有负循环，即总权重小于零的循环，Dijkstra 甚至适用于负权重。

当然有人可能会问，为什么在 templatetypedef Dijkstra 的例子中，即使没有负循环，甚至没有循环，也失败了。那是因为他正在使用另一个停止标准，一旦到达目标节点（或所有节点都已解决一次，他没有具体说明），该标准就保持算法。在没有负权重的图中，这很好用。

如果使用替代停止标准，当优先级队列（堆）为空时停止算法（此停止标准也用于问题中），那么即使对于具有负权重但没有的图，dijkstra 也会找到正确的距离负循环。

但是，在这种情况下，对于没有负循环的图，dijkstra 的渐近时间界限会丢失。这是因为当由于负权重而找到更好的距离时，可以将先前确定的节点重新插入堆中。此属性称为标签校正。

于 2014-08-06T10:54:05.217 回答
14

TL;DR：答案取决于您的实施。对于您发布的伪代码，它适用于负权重。

Dijkstra 算法的变体

关键是Dijkstra 算法有 3 种实现，但是这个问题下的所有答案都忽略了这些变体之间的差异。

  1. 使用嵌套for循环来放松顶点。这是实现 Dijkstra 算法的最简单方法。时间复杂度为 O(V^2)。
  2. 基于优先级队列/堆的实现 + 不允许重新进入，其中重新进入意味着可以将放松的顶点再次推入优先级队列以稍后再次放松。
  3. 基于优先级队列/堆的实现 + 允许重新进入。

第 1 版和第 2 版在权重为负的图上会失败（如果您在这种情况下得到正确答案，那只是巧合），但第 3 版仍然有效。

在原始问题下发布的伪代码是上面的版本 3，因此它适用于负权重。

这是Algorithm (4th edition)的一个很好的参考，它说（并包含我上面提到的版本 2 和 3 的 java 实现）：

问：Dijkstra 算法是否适用于负权重？

A. 是和不是。有两种最短路径算法称为 Dijkstra 算法，具体取决于顶点是否可以多次在优先级队列中排队。当权重为非负时，两个版本重合（因为没有顶点会被多次排队）。在 DijkstraSP.java 中实现的版本（允许一个顶点多次入队）在存在负边权重（但没有负循环）的情况下是正确的，但在最坏的情况下它的运行时间是指数级的。（我们注意到，如果边加权有向图的边权重为负，那么 DijkstraSP.java 会抛出异常，因此程序员不会对这种指数行为感到惊讶。）如果我们修改 DijkstraSP.java 使得顶点不能入队不止一次（例如，使用标记的[] 数组来标记那些已松弛的顶点），

更多实现细节以及版本3与Bellman-Ford算法的联系，请看知乎的这个回答。这也是我的回答（但用中文）。目前我没有时间把它翻译成英文。如果有人能做到这一点并在stackoverflow上编辑这个答案，我真的很感激。

于 2019-04-09T15:51:53.587 回答
11

您没有在算法中的任何地方使用 S（除了修改它）。dijkstra 的想法是一旦一个顶点在 S 上，它就不会再被修改。在这种情况下，一旦 B 在 S 中，您将无法通过 C 再次到达它。

这一事实确保了 O(E+VlogV) 的复杂性 [否则，您将多次重复边，多次重复顶点]

换句话说，您发布的算法可能不像 dijkstra 的算法所承诺的那样在 O(E+VlogV) 中。

于 2011-07-23T08:42:48.813 回答
7

由于 Dijkstra 是一种贪心方法，一旦一个顶点被标记为该循环的已访问，即使以后有另一条成本更低的路径到达它，它也永远不会被重新评估。只有当图中存在负边时，才会发生这样的问题。

贪心算法，顾名思义，总是做出当时看起来最好的选择。假设您有一个需要在给定点优化（最大化或最小化）的目标函数。贪心算法在每一步都进行贪心选择，以确保目标函数得到优化。贪婪算法只有一次机会来计算最优解，因此它永远不会回头和逆转决策。

于 2014-10-25T09:36:52.470 回答
1

考虑一下如果你在 B 和 C 之间来回移动会发生什么......瞧

（仅当图形没有方向时才相关）

编辑：我认为问题与这样一个事实有关，即在存在负权重边缘的情况下，具有 AC* 的路径只能比 AB 更好，所以在 AC 之后去哪里并不重要，假设非负权重边缘一旦您在经过 AC 后选择到达 B，就不可能找到比 AB 更好的路径。

于 2011-07-23T08:31:05.590 回答
1

"2) 我们能否使用 Dijksra 算法来计算具有负权重的图的最短路径 - 一个想法可以是，计算最小权重值，将正值（等于最小权重值的绝对值）添加到所有权重并运行 Dijksra 算法对于修改后的图。这个算法会起作用吗？

除非所有最短路径都具有相同的长度，否则这绝对行不通。例如，给定一条长度为两条边的最短路径，在每条边添加绝对值后，总路径成本增加 2 * |最大负权重|。另一方面，另一条长度为三边的路径，因此路径成本增加了 3 * |最大负权重|。因此，所有不同的路径都增加了不同的数量。

于 2017-05-22T17:20:18.837 回答
0

您可以使用不包括负循环的负边的 dijkstra 算法，但您必须允许一个顶点可以被多次访问，并且该版本将失去它的快速时间复杂度。

在那种情况下，实际上我已经看到最好使用具有正常队列并且可以处理负边缘的SPFA 算法。

于 2020-03-29T10:41:21.567 回答
0

我将只是结合所有评论来更好地理解这个问题。

可以有两种使用 Dijkstra 算法的方法：

  1. 标记已经找到与源的最小距离的节点（更快的算法，因为我们不会重新访问已经找到最短路径的节点）

  2. 不标记已经找到与源的最小距离的节点（比上面的要慢一点）

现在问题来了，如果我们不标记节点以便我们可以找到最短路径，包括那些包含负权重的路径怎么办？

答案很简单。考虑在图中只有负权重的情况：

包含负数的图。 循环)

现在，如果您从节点 0（Source）开始，您将有如下步骤（这里我没有标记节点）：

  1. 0->0 为 0, 0->1 为 inf , 0->2 为 inf 开头

  2. 0->1 为 -1

  3. 0->2 为 -5

  4. 0->0 as -8（因为我们没有放松节点）

  5. 0->1 为 -9 .. 依此类推

这个循环将永远持续下去，因此 Dijkstra 的算法在负权重的情况下无法找到最小距离（考虑到所有情况）。

这就是为什么贝尔曼福特算法用于在负权重的情况下找到最短路径，因为它会在负循环的情况下停止循环。

于 2021-07-26T20:51:55.460 回答