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


Top Users Jul 2017
  1. Bikram

    4910 Points

  2. manu00x

    2940 Points

  3. Debashish Deka

    1870 Points

  4. joshi_nitish

    1776 Points

  5. Arjun

    1506 Points

  6. Hemant Parihar

    1306 Points

  7. Shubhanshu

    1128 Points

  8. pawan kumarln

    1124 Points

  9. Arnab Bhadra

    1114 Points

  10. Ahwan

    956 Points


24,099 questions
31,074 answers
70,703 comments
29,407 users