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

Question

Dijkstra 算法是否适用于非循环图 (DAG) 的负边图？我认为这是因为没有循环，所以不可能有负循环。这个算法会失败还有其他原因吗？

谢谢[明天期中考试]

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 队列而不是优先级队列）。

Answer 2

我认为如果没有负权重，Dijkstra 算法将适用于 DAG。因为 Dijkstra 算法无法给出负加权边图的正确答案。但有时它会基于图形类型。

Answer 3

只要存在负边权重，Dijkstra 的纯实现就会失败。以下变体仍然适用于给定的问题场景。

每次边 u -> v 松弛时，将一对（newer/shorter 从源到 v 的距离）推入队列。这会导致队列中同一顶点的多个副本与源的距离不同。
继续更新距离，直到队列为空。

即使存在负边缘，上述变体仍然有效。但如果存在负权重循环则不然。 DAG 是非循环的，所以我们不必担心负循环。

有一种更有效的方法可以使用拓扑排序为 DAG 计算最短路径距离 O(V+E) 时间。可以找到更多详细信息 here

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

Dijkstra's algorithm on directed acyclic graph with negative edges

algorithm

dijkstra

directed-acyclic-graphs