We know Bellman Ford is an algorithm to find the negative cycle. And here is the algorithm for Bellman FordInput: Given a graph G(V,E) and w(e) is weightOutput: Return Yes if negative cycle exists.1: set d(s) = 0 and d(v) = 1 for all v (- s2: for i = 1 ... n-1 do3:      for every edge (u, v) in G do4:        if d(v) > d(u) + w(u,v) then5:           d(v) = d(u) + w(u,v)6:      end for7: end for8: for every edge (u, v) in G do9:     if d(v) > d(u) + w(u, v) then10:       return True11:return FalseLine 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?
why negative cycle exists if we can relax the edges one more time after running the Bellman Ford Algorithm
algorithms;dynamic programming;shortest path;correctness proof