Search code examples
algorithmbellman-ford

Can we 100% find Negative cycles in Bellman-Ford at n iteration?


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?


Solution

  • 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.