Dijkstra算法中如何处理负权重

Question

我正在尝试理解为什么Dijkstra算法不能处理带有负权重的情况。在最短路径的示例中，我试图弄清以下情况：

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

从网站上看：

假设所有边都从左到右有向，如果我们从A开始，Dijkstra算法将选择使d(A,A)+length(edge)最小的边(A,x)，即(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)
}

感谢您的来信，

Meir

- Meir

---

一般情况下，带有负边权的路径规划非常困难。无论你找到什么路线，总有可能在其中某个地方出现任意长的路线和任意大的负边权。如果这是NP完全问题，我也不会感到惊讶。 - Nick Johnson

如果有其他人也有这个疑问，可以在图形中查找最短路径，前提是该图没有负权重循环。如果松弛函数成功时返回一个“true”值，则上述算法将起作用。在这种情况下，如果相邻顶点“v”不存在，则会将其加入优先级队列，如果已经存在，则会更新。这意味着被访问过的节点会不断被添加到优先级队列中，因为它们不断被松弛。 - goelakash

Answer 1

您提出的算法可以在该图中找到最短路径，但不一定适用于所有图形。例如，考虑这个图：

让我们跟踪执行您的算法的过程。

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

请注意，虽然在此过程的末尾，d(C)仍然是0，但是到C的最短路径长度为-200。这意味着您的算法无法计算出所有节点的正确距离。此外，即使您存储从每个节点到起始节点A的返回指针，您也会从C到A走错路线。这是因为Dijkstra算法（以及您的算法）都是一种贪婪算法，假设一旦它们计算出到某个节点的距离，找到的距离就必须是最优距离。换句话说，算法不允许自己取已经扩展过的节点的距离并更改该距离。在存在负权边的情况下，您的算法和Dijkstra算法可能会“惊奇地”看到一个负成本边，从而确实减少了从起始节点到某个其他节点的最佳路径成本。

- templatetypedef

---

补充你出色的回答：Dijkstra算法作为一种贪心算法，正是因为其短视的选择，导致了算法的局限性。 - blubb

我想指出的是，在技术上，由于负循环 A,D,B,A，这个图中所有路径的成本都为负无穷。 - Nate

为了澄清，图中所有的边都是从左到右有向的。在我的高质量 ASCII 艺术中描绘箭头有点困难。 :-) - templatetypedef

对于那些之前没见过带有负边的图表的人，我认为这个图表的一个有用的解释是一张收费高速公路的网络，边的权重表示你需要支付的过路费。其中-300的路是一条疯狂的反向收费路，他们会给你$300。 - Chiara Coetzee

这是Dijkstra算法的工作原理。该算法不会探索路径，而是通过处理节点来工作。每个节点仅被处理一次，因此一旦我们处理了B节点并得到其距离为1，我们将永远不会重新访问节点B或尝试更新它的距离。 - templatetypedef

Answer 2

注意，如果图形没有负循环，即循环的加权总和小于零，则Dijkstra算法即使对于负权重也有效。

当然，人们可能会问，在由templatetypedef制作的示例中，即使没有负循环，事实上甚至没有循环，为什么Dijkstra算法会失败。那是因为他正在使用另一个停止准则，一旦到达目标节点（或所有节点都已解决，他没有明确说明）就会阻止算法。在没有负权重的图中，这样做很好。

如果使用替代停止准则，在优先级队列（堆）运行为空时停止算法（问题中也使用了这种停止准则），则Dijkstra算法即使对于带有负权重但没有负循环的图形也能找到正确的距离。

然而，在这种情况下，Dijkstra算法对没有负循环的图形的渐近时间界丢失了。这是因为由于负权重的存在，以前解决的节点可以重新插入到堆中，当发现更好的距离时。这种属性称为标签修正。

- infty10000101

---

目前不清楚您为什么认为时间会更像Bellman-Ford，而不是指数级别（这比Bellman-Ford更糟糕）。您是否有具体的算法和证明？ - Gassa

你可以使用完全相同的Dijkstra算法实现，并使用提到的停止条件，在队列为空时停止（请参见原问题中的伪代码）。即使它表现出不同的行为，多次解决节点（标签校正），它仍然是最短路径的Dijkstra算法。 - infty10000101

对于第二点：那只是我的猜测，所以我会将其删除。我认为你说的指数时间是正确的，因为有指数多的路径需要探索。 - infty10000101

如果你应用了标签修正，那么它不再是最短路径，但根据定义可能是最短路径。或者我错了。 - tbuglc

Answer 3

简述：答案取决于你的实现方式。对于您发布的伪代码，它适用于负权重。

---

Dijkstra算法的变体

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

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

第1和第2版本将无法处理带有负权重的图（如果在这种情况下得到正确答案，那只是巧合），但是第3版仍然有效。

原问题中发布的伪代码是上面提到的第3个版本，因此它适用于负权重。

这里有一个好的参考来源来自算法（第四版），其中提到了我上面提到的第2和第3个版本的Java实现：

Q. Dijkstra算法适用于带有负权重的图吗？

A. 是和不是。有两种最短路径算法称为迪杰斯特拉算法，取决于一个顶点是否可以在优先队列上多次入队。当权重为非负时，这两个版本相同（因为没有顶点会被多次入队）。DijkstraSP.java 中实现的版本（允许一个顶点多次入队）在存在负边权（但没有负环）的情况下是正确的，但其运行时间在最坏情况下呈指数级增长。（我们注意到，如果带权有向图具有负权重边，则 DijkstraSP.java 将抛出异常，以便程序员不会对这种指数行为感到惊讶。）如果我们修改 DijkstraSP.java 以使一个顶点不能多次入队（例如使用 marked[] 数组标记那些已经被放松的顶点），则该算法保证在 E log V 时间内运行，但在存在负权边时可能产生错误结果。

有关更多实现细节以及版本 3 与 Bellman-Ford 算法的联系，请参见知乎上的这篇答案。这也是我的回答（但是是中文）。目前我没有时间将其翻译成英语。如果有人能够完成这项工作并在 stackoverflow 上编辑此回答，我将不胜感激。

- soloice

---

我在考虑处理负权重（如果我们确定没有负环）的版本3的时间复杂度。它不应该是O（V * E）吗？ - banna

有趣，但我认为版本3不再是Dijkstra算法，实际上它是SPFA（https://en.wikipedia.org/wiki/Shortest_path_faster_algorithm），这是Bellman-Ford的修改/优化版（因为它遵循Dijkstra的想法来最小化Bellman的松弛步骤数量）。Dijkstra假设从一个节点开始的任何路径始终导致更大的距离（正权重边），这就是为什么它不需要在访问/关闭节点时重新计算，这使它比原始的Bellman-Ford算法更快。 - Hoang Dao

Answer 4

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

这个事实确保了复杂度为O(E+VlogV)【否则，你会重复遍历边和顶点】。

换句话说，你发布的算法可能不符合Dijkstra算法所承诺的O(E+VlogV)的复杂度。

- amit

---

此外，无需修改没有负权边的顶点，这完全违反了路径成本只能随着重复边增加的假设。 - prusswan

这个假设正是允许我们使用S的原因，并且“知道”一旦一个顶点在S中，它将永远不会再被修改。 - amit

你的最后一句话是错误的。当算法在没有负边的图上运行时，其时间复杂度为O（E + VlogV）。没有必要检查我们是否已经访问了一个节点，因为它已经被访问的事实保证了松弛过程不会再次将其添加到队列中。 - Egor Okhterov

Answer 5

由于Dijkstra算法是一种贪心算法，一旦一个顶点在此循环中被标记为已访问，即使后面还有更便宜的路径到达该顶点，也不会再次重新评估。只有当图中存在负边时，这样的问题才会出现。

---

正如其名称所示，贪心算法总是选择当前看起来最好的解决方案。假设您有一个目标函数需要在给定点进行优化（无论是最大化还是最小化），贪心算法在每个步骤都做出贪心选择以确保目标函数得到优化。 贪心算法只有一次计算最优解的机会，因此它永远不会后退和撤消决策。

- punchoyeah

Answer 6

考虑在B和C之间来回移动会发生什么...哇

(仅当图不是有向图时相关)

编辑： 我认为问题与AC*路径只有在存在负权边时才能比AB更好有关，因此，在假设非负权边的情况下，一旦选择在AC后到达B，就不可能找到比AB更好的路径。

- prusswan

---

这是不可能的，图是有向的。 - amit

@amit：好观点，我忽略了那个。是时候重新考虑这个问题了。 - prusswan

Answer 7

"2) 我们能在带有负权重的图中使用Dijksra算法来寻找最短路径吗？一种想法是，计算最小权重值，将一个正值（等于最小权重值的绝对值）添加到所有权重中，并对修改后的图运行Dijksra算法。这个算法有效吗？"

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

- Wackyfool

Answer 8

你可以使用Dijkstra算法处理带有负边权的图，但是必须允许一个顶点被多次访问，这种版本将失去其快速的时间复杂度。

在这种情况下，实际上我发现最好使用SPFA算法，它具有普通队列并且可以处理负边权。

- CodingLab

Answer 9

我将把所有的评论结合起来，以更好地理解这个问题。

使用Dijkstra算法有两种方式：

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

2. 不标记已经从源节点找到最小距离的节点（比上面的方法稍微慢一些）

现在问题出现了，如果我们不标记节点，那么如何找到包含负权重的最短路径呢？

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

)

现在，如果你从节点0（源）开始，你将需要这些步骤（在这里我不标记节点）：

1. 一开始，0->0为0，0->1为inf，0->2为inf

2. 0->1为-1

3. 0->2为-5

4. 由于我们没有松弛节点，0->0为-8

5. 0->1为-9...如此往复

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

这就是为什么 Bellman Ford 算法被用来在负权重的情况下找到最短路径，因为它会在出现负循环的情况下停止循环。

- Yash Singhal