我们可以改变Dijkstra的算法来处理负权重吗？

Question

来自维基百科的伪代码:

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的算法不会这样改变呢？

Answer 1

你当然可以Dijkstra算法的工作负值,只需确保你不经过任何节点或边缘的两倍.在这里,通过工作,我的意思是终止.然而,结果可能不是最佳的.

Dijkstra的算法有一种贪婪的感觉.想象一下下面的图:

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

如果我们想从A到B,最好的路径是ACDB,但Dijkstra的算法找到AB.你不能让Dijkstra的算法预测未来,因为它是一个贪婪的算法.通过预测未来,我的意思是,稍后知道路径的成本可能会降低.请注意,这意味着如果将修改应用于Dijkstra算法的版本,只要看到目标就会终止,则修改将无法正常工作.在您发布的版本中,您的修改工作正常,除了有更有效的方法来处理负边缘(请参阅注释).

作为旁注,具有负值的无向图中的最短路径或具有负循环的有向图甚至没有意义!

Answer 2

Dijkstra可以一次访问每个节点,因为当它选择要访问的新节点时,他会从根节点中选择具有最短路径的非访问节点.因此,他可以安全地假设没有更短的方式通过另一个非访问节点进入该节点(因为如果从A到B知道的最佳方式成本为2,从A到C的最佳方式成本为3,没有机会找到从A到B的更好的方法,例如A> C> B).

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

您当然可以使用建议的修改,但是您将失去仅访问每个节点一次的好处; 因此,与Ford-Bellman等其他算法相比,它会失去性能