algorithm - Dijkstra算法的负周期

因此，我完全理解为什么负边缘权重不适用于Dijkstra算法，例如：

       A
      / \
     /   \
    /     \
   5       2
  /         \
  B--(-10)-->C

然而，我读到“如果图中有任何负循环，你永远不会停止更新顶点的距离。这将导致一个无限循环，“我不明白如果我们在访问顶点时声明顶点“完成”会是什么情况。如果我们不能重新访问已经访问过的顶点，我们怎么可能进入一个循环？

最佳答案

您所描述的版本确实可以避免循环在最低成本路径具有负边缘的情况下，它也可能无法发现正确的最低成本路径，但有一个没有负边缘的更直接的路径。

关于algorithm - Dijkstra算法的负周期，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/51904021/