Negative cycle detection using Bellman-Ford and its correctness

Question

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:

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. 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?

Answer 1

If there are no negative cycles then you can indeed perform the relaxation until all values remain the same. In the $i$-th round of relaxation you are ensured to have correctly computed all finite distances towards all vertices whose hop-distance from $s$ is at most $i$ (the hop distance is the number of edges in a shortest path).

Therefore stopping after the $(n-1)$-th iteration ensures that:

• All finite distances have been correctly computed
• The algorithm terminates on graphs with negative cycles.

Notice that there are graphs where all $(n-1)$ iterations are needed to properly compute the distances. E.g., a path.

Regarding 2), your question is not completely clear to me. In the proof there is no particular edge to visualize. The proof just shows that if it impossible for these two conditions to be simultaneously true:

• There is some negative weight cycle $C$.
• No relaxation happens, i.e., $v.d \le u.d + w(u,v)$ for all vertices $v$ of the cycle. This is used in the second centered inequality.