1
$\begingroup$

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.

2 Answers 2

1

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?
  • 0
    Also helpful: http://cs.stackexchange.com/a/6914/394632015-12-02
0

in the k-th iterion of the Bellman-Ford algorithm : the dist(s,v) the algorithm marks a vertice v will remain unchanged (thus correct) for all vertices v such that the lightest path from s to v is of length k. This can be proven by induction. note that any path is of length <= |V|-1.