Is Bellman Ford Dynamic Programming approach ?

Question

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 ?

Answer 1

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 i^th 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/

Answer 2

Bellman-ford we use data structure an array of size as no. of vertex and we update it looking at graph data structure in adj. matrix or adj. list. We run n times RELAX function for each edge. We never accept on each iteration the RELAXed value to be answer. We wait to run it n times. And we use the updated value of vertex weight in each iteration of data structure. i.e. This algorithm is completely rely on updating and using the stored value.

While Djkastra is based on finding best solution in each round. Which after n run combines to bring us the solution.