如果Dijkstra算法运行在负权重周期的有向图上，会发生什么情况？

Question

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

Answer 1

问题不在于Dijkstra的算法不会终止，而在于Dijkstra的算法不适用于负权重图。请参阅this answer以解释原因。