GATE CSE
First time here? Checkout the FAQ!
x
0 votes
348 views
Is bellman ford a dynamic programming approach? If yes, what is the reason behind it? How do we find an optimal substructure and overlapping sub problems in this ?
asked in Algorithms by (137 points)   | 348 views

1 Answer

+2 votes

Yes. It works in dynamic programming approach.

  • It calculates shortest paths in bottom-up manner.
  • Intermediate values are stored and used for next level values.
  • It first calculates the shortest distances for the shortest paths which have at-most one edge in the path. Stores it. 
  • Then, it calculates shortest paths with at-most 2 edges, and so on.
  • After the ith iteration of outer loop, the shortest paths with at most i edges are calculated.

Hence it follows Dynamic programming approach

For more details , please refer : http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/

 

answered by Veteran (24.7k points)  


Top Users Apr 2017
  1. akash.dinkar12

    3660 Points

  2. Divya Bharti

    2580 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Debashish Deka

    1614 Points

  7. Shubham Sharma 2

    1610 Points

  8. Prashant.

    1492 Points

  9. Arjun

    1472 Points

  10. Arunav Khare

    1464 Points

Monthly Topper: Rs. 500 gift card

22,088 questions
28,063 answers
63,298 comments
24,173 users