# why negative cycle exists if we can relax the edges one more time after running the Bellman Ford Algorithm

We know Bellman Ford is an algorithm to find the negative cycle. And here is the algorithm for Bellman Ford Input: Given a graph G(V,E) and w(e) is weight Output: Return Yes if negative cycle exists.

1: set d(s) = 0 and d(v) = 1 for all v (- s
2: for i = 1 ... n-1 do
3:      for every edge (u, v) in G do
4:        if d(v) > d(u) + w(u,v) then
5:           d(v) = d(u) + w(u,v)
6:      end for
7: end for
8: for every edge (u, v) in G do
9:     if d(v) > d(u) + w(u, v) then
10:       return True
11:return False


Line 8 - Line 11 is the doing one more relax to detect the negative cycle, but why these lines guarantee detect the negative cycle if have one in the graph?

• What research have you done? What textbooks/lecture notes have you read? What have you tried on your own, to try to answer this? Did you try to prove the claim yourself? Where did you get stuck? We expect you to make a serious effort to research the problem on your own before asking here. – D.W. Jun 25 '14 at 21:46

If there is a negative cycle, then it is guaranteed that $d(v)$ will decrease on each iteration for each vertex $v$ in a negative cycle, since as we do more iterations of Bellman-Ford we're considering paths that traverse that negative cycle more and more times. The more you traverse a negative cycle, the more negative the length of that path becomes. Therefore, it's guaranteed that if the graph has a negative cycle, then this algorithm will detect it, because it'll see the value of some $d(v)$ decrease.