The Gateway to Computer Science Excellence
+2 votes
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 ?
in Algorithms by (157 points) | 2.9k views

1 Answer

+4 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 :

by Boss (33k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,370 answers
105,272 users