使用Dijkstra算法的负权重

 

我想了解为什么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)
}

谢谢，

梅厄

你所建议的算法确实会在这个图中找到最短路径，但并不是所有的图都是一般的。 例如，考虑这个图表：

图的图

假设边缘从左到右如您的示例中所示，

你的算法将如下工作：

  • 首先，将d(A)设置zero ，将其他距离设置为infinity 。
  • 然后展开节点A ，将d(B)设置为1 ，将d(C)设置zero ，将d(D)为99 。
  • 接下来，你展开C ，没有净变化。
  • 然后你展开B ，这没有效果。
  • 最后，展开D ，它将d(B)更改为-201 。

    • 注意，尽管到C的最短路径长度为-200 ，但d(C)仍然为0 。 因此，在某些情况下，您的算法无法准确计算距离。 而且，即使您要存储指向如何从每个节点到起始节点A指针，您也会结束从C到A的错误路径。

    请注意，如果图表没有负循环，即加权总和小于零的循环，那么Dijkstra即使对负权重也适用。

    当然，有人可能会问，为什么在templatetypedef所做的例子中，即使没有负循环，Dijkstra也失败了，事实上甚至没有循环。 这是因为他正在使用另一个停止标准，该标准在达到目标节点后立即保存算法（或者所有节点已经解决一次，他没有完全指定）。 在没有负重的图表中，这可以正常工作。

    如果一个人使用可替代停止准则，当优先级队列（堆）运行空时停止算法（该停止标准也被用在问题中使用），则Dijkstra算法将找到正确的距离，即使是负的权重，但没有图负循环。

    但是，在这种情况下，没有负循环的图的dijkstra的渐近时间范围就会丢失。 这是因为当由于负权重而发现更好的距离时，先前安置的节点可以重新插入到堆中。 这个属性被称为标签校正。

    你没有在算法的任何地方使用S（除了修改它）。 dijkstra的概念曾经是S上的一个顶点，它不会再被修改。 在这种情况下，一旦B在S内，你将不会再通过C达到它。

    这个事实确保了O（E + VlogV）的复杂性[否则，你会重复多次一次的边，并且多于一次的顶点]

    换句话说，您发布的算法可能不在O（E + VlogV）中，正如dijkstra的算法所承诺的那样。

    链接地址: http://www.djcxy.com/p/35183.html

    上一篇: Negative weights using Dijkstra's Algorithm

    下一篇: Am I using the correct format pattern for parsing a date?