Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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?
share|improve this answer
    
@bird234: let me know if these hings weren't enough –  Ernest Jul 17 '11 at 4:47
    
Thanks a lot. Assuming that you meant the shortest path to a certain vertex by 'minimum path', I think the answer to the 'Strong hint' is Yes. Am I correct? The number of iterations will be taken to find that shortest path is dependent on which order the edges are relaxed in each iteration. Please correct me if I am wrong. Thanks again. –  bird234 Jul 17 '11 at 6:22

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.