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?