If the distance between two points drops at n iteration,we know there must be a negative cycle. My question is that if there is a negative cycle, will the distance between two points 100% drop at n iteration?

CodePudding user response：

Not two arbitrary points, but yes, if the graph has a negative cycle, then Bellman-Ford will update at least one distance in every iteration, no matter how many iterations you do.

The distances on the negative cycle get smaller and smaller, approaching -infinity.