使用Dijkstra算法的负权重

Question

我试图理解为什么Dijkstra的算法不适用于负权重.阅读最短路径上的示例,我试图找出以下场景:

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

来自网站:

假设边缘全部从左向右指向,如果我们从A开始,Dijkstra算法将选择最小化d(A,A)+长度(边缘)的边(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)
}

谢谢,

梅厄

Answer 1

您建议的算法确实会在此图中找到最短路径,但不是所有图形.例如,请考虑以下图表:

假设边缘从左到右指向,如示例所示,

您的算法将按如下方式工作:

1. 首先,您设置d(A)为zero和其他距离infinity.
2. 然后,展开节点A,设置d(B)为1,d(C)to zero和d(D)to 99.
3. 接下来,展开C,没有净更改.
4. 然后展开B,这没有任何效果.
5. 最后,您展开D,更改d(B)为-201.

请注意,在本月底,不过,d(C)仍然是0,即使最短路径C长度为-200. 因此,在某些情况下,您的算法无法准确计算距离.此外,即使你要存储指针说明如何从每个节点到达起始节点A,你也可以从错误的路径返回C到A.

Answer 2

注意,如果图表没有负周期,即负累加权小于零的周期,Dijkstra甚至可以用于负权重.

当然有人可能会问,为什么在templatetypedef Dijkstra所做的例子中,即使没有负循环,实际上也没有循环.这是因为他正在使用另一个停止标准,一旦达到目标节点就保持算法(或者所有节点已经安置一次,他没有确切地指定).在没有负权重的图表中,这很好.

如果正在使用替代停止标准,当优先级队列(堆)运行为空时停止算法(此问题中也使用此停止标准),那么即使对于负权重但没有的图形,dijkstra也会找到正确的距离负循环.

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

Answer 3

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上编辑这个答案，我真的很感激。

Answer 4

你没有在算法的任何地方使用S(除了修改它).dijkstra的想法曾经是一个顶点在S上,它将不再被修改.在这种情况下,一旦B在S内部,您将无法通过C再次到达它.

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

换句话说,你发布的算法可能不在O(E + VlogV)中,正如dijkstra算法所承诺的那样.

Answer 5

由于Dijkstra是一种贪婪的方法,一旦顶点被标记为此循环的访问,即使有另一条路径以较低的成本稍后到达它,它也永远不会再次重新评估.这种问题只有在图中存在负边时才会发生.

一个贪心算法,顾名思义,总是让这似乎是在那一刻的最佳选择.假设您有一个需要在给定点优化(最大化或最小化)的目标函数.贪婪算法在每一步都做出贪婪的选择,以确保目标函数得到优化.Greedy算法只有一次计算最佳解决方案,因此它永远不会返回并反转决策.