具有负边的有向无环图的Dijkstra算法

Question

如果Dijkstra算法是非循环的(DAG),那么Dijkstra算法会在带有负边的图上工作吗？我认为这是因为没有循环就不会有负循环.这个算法失败还有其他原因吗？

谢谢[明天中期]

Answer 1

考虑图(指示1 -> 2, 2-> 4, 4 -> 3, 1 -> 3, 3 -> 5):

  1---(2)---3--(2)--5
  |         |
 (3)      (2)
  |         |  
  2--(-10)--4

最低路径是1 - 2 - 4 - 3 - 5成本-3.但是,Dijkstra将d[3] = 2, d[2] = 3在第一步中设置,然后3从其优先级队列中提取节点并进行设置d[5] = 4.由于节点3是从优先级队列中提取的,并且Dijkstra不会将给定节点多次推送到其优先级队列,因此它将永远不会再次进入其中,因此该算法将无法工作.

Dijkstra的算法不适用于负边缘,周期.没有一个周期没有改变.Bellman-Ford是能够检测负成本周期并与负边缘一起工作的人.如果你有负边缘,Dijkstra将不起作用.

如果您更改Dijkstra的算法,使其可以多次将节点推送到优先级队列,则算法将使用负成本边缘.但是,如果新算法仍然是Dijkstra的话,那就值得商榷:我会说你这样得到Bellman-Ford,这通常就是这样实现的(好吧,通常使用FIFO队列而不是优先级队列).