GATE CSE
First time here? Checkout the FAQ!
x
0 votes
206 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)   | 206 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 (20.6k points)  

Related questions

0 votes
2 answers
2
asked in Algorithms by vaishali jhalani Boss (6k points)   | 136 views
0 votes
2 answers
3
Top Users Feb 2017
  1. Arjun

    5278 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3942 Points

  4. Aboveallplayer

    3086 Points

  5. Debashish Deka

    2378 Points

  6. sriv_shubham

    2308 Points

  7. Smriti012

    2236 Points

  8. Arnabi

    2008 Points

  9. sh!va

    1672 Points

  10. mcjoshi

    1660 Points

Monthly Topper: Rs. 500 gift card

20,856 questions
26,009 answers
59,671 comments
22,107 users