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

Question

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?

Answer 1

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.

This should be covered in standard textbooks and lecture notes on Bellman-Ford. There's not much point in having us reiterate those standard proofs again; if we don't know why you didn't understand the standard explanation, it's hard for us to write an explanation that you will help you.