7

取自维基百科的伪代码： 

function Dijkstra(Graph, source):
 2      for each vertex v in Graph:                                // Initializations
 3          dist[v] := infinity ;                                  // Unknown distance function from source to v
 4          previous[v] := undefined ;                             // Previous node in optimal path from source
 5      end for ;
 6      dist[source] := 0 ;                                        // Distance from source to source
 7      Q := the set of all nodes in Graph ;                       // All nodes in the graph are unoptimized - thus are in Q
 8      while Q is not empty:                                      // The main loop
 9          u := vertex in Q with smallest distance in dist[] ;    // Start node in first case
10          if dist[u] = infinity:
11              break ;                                            // all remaining vertices are inaccessible from source
12          end if ;
13          remove u from Q ;
14          for each neighbor v of u:                              // where v has not yet been removed from Q.
15              alt := dist[u] + dist_between(u, v) ;
16              if alt < dist[v]:                                  // Relax (u,v,a)
17                  dist[v] := alt ;
18                  previous[v] := u ;
19                  decrease-key v in Q;                           // Reorder v in the Queue
20              end if ;
21          end for ;
22      end while ;
23      return dist[] ;
24  end Dijkstra.

现在，在第 14 行中，我们看到松弛仅应用于u尚未从 中删除的邻居Q。但是，如果我们也把它的邻居u从 中删除Q，在我看来，该算法确实适用于负权重。我没有发现任何与此主张相矛盾的实例。

那么为什么 Dijkstra 的算法没有这样改变呢？

4

6 回答 6

13

您当然可以使 Dijkstra 的算法在负值下工作，只需确保您不遍历任何节点或边两次。在这里，工作，我的意思是终止。然而，结果可能不是最佳的。

Dijkstra 的算法对它有一种贪婪的感觉。想象一下下图：

A --- 1 --- B
|           |
3          -4
|           |
C -- -1 --- D

如果我们想从 A 到 B，最好的路径是 ACDB，但 Dijkstra 的算法会找到 AB。你不能让 Dijkstra 的算法预测未来，因为它是一个贪心算法。通过预测未来，我的意思是知道以后，路径的成本可能会降低。请注意，这意味着如果将修改应用于 Dijkstra 算法的一个版本，该版本会在看到目标后立即终止。在您发布的版本中，您的修改工作除了有更有效的方法来处理负边缘（见评论）。

附带说明一下，具有负值的无向图或具有负循环的有向图中的最短路径甚至没有意义！

于 2012-05-29T13:24:22.227 回答
6

Dijkstra 可以一次访问每个节点，因为当它选择要访问的新节点时，他会选择从​​根节点开始具有最短路径的未访问节点。因此，他可以安全地假设没有更短的方法可以通过另一个未访问的节点到达该节点（因为如果您知道从 A 到 B 的最佳方式成本为 2，而从 A 到 C 的最佳方式成本为 3，没有机会找到从 A 到 B 的更好方法，例如 A>C>B)。

如果你添加负权重，你会突然打破这个假设。

您当然可以使用您建议的修改，但是您将失去只访问每个节点一次的好处；因此，与其他算法（例如 Ford-Bellman）相比，它会失去性能增益

于 2012-05-29T13:44:45.433 回答
4

你基本上有两个选择。

  1. 您可以根据建议更改算法。如果你有没有负循环的有向图，那么这是一个正确的算法，但它可能真的很慢（因为你会多次访问每个节点）。我认为存在这种算法具有指数时间复杂度的情况。

  2. 您可以通过使用潜力来改变边际成本。每个顶点都有一些潜在的 h(v)，边 u->v 的权重将为 w(u,v) + h(u) - h(v)。请注意，这不会影响给定两个顶点 (s, t) 之间的哪条路径最短，只是它的成本会被 h(s) - h(t) 改变。但是你需要计算潜力。这里建议这样做的好方法：http ://en.wikipedia.org/wiki/Johnson's_algorithm

于 2012-05-29T13:55:47.757 回答
3

不，不可能如所述。该算法对负权重没有意义，除非您严格限制提供的图形类型。

假设一个图有节点 A、B、C 和权重 AB=-1、BA=0、BC=1 的边。

现在 A 和 C 之间不再存在最短路径，您总是可以通过在 A 和 B 之间再来回走一次来缩短路径。

当然，算法仍然会运行，但它会给出错误的答案。

于 2012-05-29T13:20:55.707 回答
2

是的，您的修改将在您未提及的 2 个假设下起作用，但我想这是暗示的：

  1. 最短路径必须在您的输入图中实际定义。如果你放弃对非负权重的限制，你至少必须要求没有负权重的循环。
  2. 第 19 行中的“减少 Q 中的键 v”操作对于不在 Q 中的节点 v 并没有真正意义。但是，当然，您可以使用新值将它们重新添加到 Q 中。

但是，您会失去 Dijkstra 算法的一个重要特性：它具有良好的最坏情况渐近性能。现成的 Dijkstra 保证了良好的性能，因为它最多访问每个节点和每个边一次。包含您的更改后，已删除的节点可以重新添加到优先级队列中，并且可能必须一遍又一遍地访问图表的大部分。在最坏的情况下，您必须执行与 Bellman-Ford 算法一样多的松弛，但是您有优先级队列的额外开销。这会使您在最坏情况下的性能比 Bellman-Ford 更差，因此对于带有负边的图来说这是首选。

这并不意味着您修改后的 Dijkstra 没有用。如果负边很少和/或如果这些负边通过昂贵的路径与图的其余部分分开，它可以比 Bellman-Ford 表现得更好。但是要为非常糟糕的最坏情况做好准备。

于 2014-11-19T19:48:42.530 回答
1

好吧，仅仅放松 Dijkstra 的修改版本中已经访问过的节点是不够的（它会在包含负边的图中给你一个错误的答案）。此外，您需要将任何宽松的边缘放入您的容器中（例如，优先级队列或仅队列）。因此，您可以将第 19 行的代码修改为：

if v is in priority queue
    then decrease-key(v)
else
    add v into priority queue

在这种情况下，您的算法可以工作。此外，对于正加权图，修改版 Dijkstra 的效率不会降低。这很容易证明，因为这自然是一个贪心算法。

但是，对于包含负边的图，新算法在理论分析方面可能会变慢，但在实践中会很好。

其实你可以看看段丁凡在中国（1994）发表的一种名为SPFA（Shortest Path Faster Algorithm）的算法。许多 OIer（信息奥林匹克）都知道这种算法有时可能会击败 Dijkstra。

于 2013-11-07T09:56:55.553 回答