How Bellman ford is dynamic programming?

Question

 What is the reason behind it? How do we find an optimal substructure and overlapping sub problems in this ? In which line of code memoization is done?
BELLMAN-FORD(G,w,s)
Code
1.  INITIALIZE-SINGLE-SOURCE(G,s)
2.  for i = 1 to |G.V|-1
3.     for each edge (u,v) ∈ G.E
4.        RELAX(u,v,w)
5.  for each edge (u,v) ∈ G.E
6.     if v.d > u.d + w(u,v)
7.        return FALSE
8.  return TRUE

INITIALIZE-SINGLE-SOURCE(G,s)
1.  for each vertex v ∈ G.V
2.     v.d = ∞
3.     v.pi = NIL
4.  s.d = 0

RELAX(u,v,w)
1.  if v.d > u.d + w(u,v)
2.     v.d = u.d + w(u,v)
3.     v.pi = u

Comments

what my suggestion ( neither request nor order ),

take a graph ( which is connected )

blindly apply your code on that, do it step by step, note each step

it will help you

---

I really did , and I understood why it's dynamic and how previous stored distance to vertex is used to calculate distance for other vertex. Thanks.

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