cycle - 如果 Dijkstra 算法在具有负权重循环的有向图上运行会发生什么？

Question

假设 Dijkstra 从随机顶点运行，并且在路径上遇到负权重循环。我们可以循环循环以使成本尽可能小，但 Dijkstra 的不变量不是“重新访问”访问过的节点，所以我想不会有无限循环并且 Dijkstra 会终止？

Answer 1

问题不在于 Dijkstra 的算法不会终止，而是 Dijkstra 的算法根本不适用于具有负权重的图。有关原因的解释，请参见此答案。