Sportsman's blog

Test case where Bellman-ford must go till (V-1)th iteration to give the right answer?
By Sportsman, history, 4 years ago, In English

I recently came across the Bellman-ford algorithm and tried to understand the intuition behind, why the Bellman-Ford algorithm takes atmost V-1 iterations to give the correct ouput. It would be helpful if you could share the reason or probably a test case or both, so that i can do a dry run to digest it. Thanks!

  • Vote: I like it
  • -23
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
4 years ago, # |
← Rev. 3   Vote: I like it +17 Vote: I do not like it

If the shortest path between $$$s$$$ and $$$t$$$ has $$$k$$$ edges, Bellman Ford will find it after at most $$$k$$$ iterations. Since a shortest path cannot have more than $$$V-1$$$ edges, it takes at most that many iterations.

Consider a line graph with $$$n$$$ nodes, with node $$$i$$$ connected to node $$$i+1$$$. You run Bellman Ford from node $$$1$$$ and process the edges further away from $$$1$$$ first. Then it will take exactly $$$n-1$$$ steps.

→ Reply