I recently started studying algorithms on my own using corman and mit algo videos in youtube. I am going thru bellman ford.
I have 2 doubts in correctness of algorithm
1) why are we relaxing (num of vertices – 1) times all the edges. Why not some finite number of times till earlier values and new values remain same.
2) Second for loop(lines 5,6,7 in algo image) is for detecting negative edge cycle. THen i have gone through this correctness. I have seen a theorem that if there is a negative edge cycle reachable from source s then we can find an edge uv such that d(v)>d(u)+w(u,v) [I understood the proof by contradiction(if summing all vertices of negative edge cycle results in sum of all weights along negative cycle positive which means contradiction as it must be negative – page 2 of https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture14.pdf]
But i am not able to visualise such an edge if i have some negative edge cycle from source vertes s. Please help me how such edge exists?