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