algorithm - 使用 Dijkstra 算法的负循环

Question

因此，我完全理解为什么负边权重不适用于 Dijkstra 算法的原因如下:

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

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

Answer 1

您描述的版本确实会避免循环。如果最低成本路径具有负边，但存在更直接的路径但没有负边，它也可能无法发现正确的最低成本路径。