[Math] Bellman-Ford algorithm: why V-1 number of relaxation iterations

algorithmsanalysisgraph theory

Why does Bellman-Ford algorithm perform V-1 number of relaxation iterations?

I feel that it is correct when going through examples. But how do we explain it for the general case?

I have gone through the proof of correctness, and yeah, that is where the answer is, BUT what I am looking for is a simple explanation, not a mathematical proof.

I need a simple explanation in someone's own words.

I would really appreciate any effort made to help.

Thanks.

Best Answer

I won't give the answer right away, but give you hints. I think you should try to get the answer by reading as few hints as possible.

  1. What is the algorithm supposed to do, find paths or walks or what?

  2. What's the characteristic of all paths/walks found after the first iteration? What do the paths/walks found after the second iteration have in common?

Strong hint:

  1. If a graph has a minimum path of length 10, can the algorithm find it before the fifth iteration? Why? Can it find a minimum path of length 3 before the fifth iteration? Why?
Related Question