我们能在Bellman-Ford的n次迭代中100%找到负循环吗

Question

如果两个点之间的距离在n次迭代时下降，我们知道一定存在负循环。我的问题是，如果存在负循环，那么在n次迭代时，两点之间的距离会100%下降吗？

Answer 1

不是两个任意点，但是的，如果图有负循环，则Bellman-Ford将在每次迭代中更新至少一个距离，无论您进行多少次迭代。

负循环上的距离越来越小，接近-无穷大。