I recently started studying algorithms on my own using Cormen and MIT algo videos in YouTube. I am going thru Bellman-Ford.
I have 2 doubts about the correctness of the algorithm:
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?
The second for loop (lines 5,6,7 in algo image) is for detecting negative edge cycles. 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 vertex s. Please help me: how can such an edge exist?