Блог пользователя Sportsman

Test case where Bellman-ford must go till (V-1)th iteration to give the right answer?
Автор Sportsman, история, 4 года назад, По-английски

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!

  • Проголосовать: нравится
  • -23
  • Проголосовать: не нравится

»
4 года назад, # |
← Rev. 3   Проголосовать: нравится +17 Проголосовать: не нравится

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.

→ Ответить