带负边的有向无环图的Dijkstra算法 [英] Dijkstra's algorithm on directed acyclic graph with negative edges

问题描述

如果Dijkstra的算法是非循环的（DAG），那么该算法是否可以在具有负边的图形上使用？我认为是因为没有周期，所以不可能有负循环。

Will Dijkstra's algorithm work on a graph with negative edges if it is acyclic (DAG)? I think it would because since there are no cycles there cannot be a negative loop. Is there any other reason why this algorithm would fail?

感谢[明天中期]

推荐答案

考虑图表（指向 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不会多次将给定节点推送到其优先级队列，因此它将永远不会再次出现在该节点中，因此该算法将无法工作。

The minimum path is 1 - 2 - 4 - 3 - 5, with cost -3. However, Dijkstra will set d[3] = 2, d[2] = 3 in the first step, then extract node 3 from its priority queue and set d[5] = 4. Since node 3 was extracted from the priority queue, and Dijkstra does not push a given node to its priority queue more than once, it will never end up in it again, so the algorithm won't work.

Dijkstra的算法不适用于负边沿，周期。没有周期不会改变任何东西。 Bellman-Ford是可以检测负成本周期并使用负边缘的工具。如果您有负边缘，Dijkstra将不起作用。

Dijkstra's algorithm does not work with negative edges, period. The absence of a cycle changes nothing. Bellman-Ford is the one that can detect negative cost cycles and works with negative edges. Dijkstra will not work if you can have negative edges.

如果您更改Dijkstra的算法，使其可以将节点多次推送到优先级队列，则该算法将负成本优势。但是，如果新算法仍然是Dijkstra的算法，这是有争议的：我想您会以这种方式实现Bellman-Ford，这种实现通常是完全一样的（嗯，通常使用FIFO队列而不是优先级队列）。

If you change Dijkstra's algorithm such that it can push a node to the priority queue more than once, then the algorithm will work with negative cost edges. But it is debatable if the new algorithm is still Dijkstra's: I would say you get Bellman-Ford that way, which is often implemented exactly like that (well, usually a FIFO queue is used and not a priority queue).

这篇关于带负边的有向无环图的Dijkstra算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！