使用 Dijkstra 算法的负循环

Question

所以我完全理解为什么负边权重不能与 Dijkstra 算法一起使用，例如：

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

但是，我读到 "if there is any negative cycle in graph you would never stop updating distance in vertices. This will cause a infinite loop." 我不明白如果我们在访问顶点时声明顶点 "done" 会怎样。如果我们不能重新访问我们已经访问过的顶点，我们怎么能进入一个循环？

Answer 1

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