as this is a dp approach , but i am unable to visualise the overlapping subproblems as we are iterating each edge v-1 times.
Query regarding overlapping subproblems
hello @Parmeet-Kalsi-1631789033630118
it will have overllapping subproblems becuase to find k length path we are depending in k-1 lenght path.
How does this work? Like other Dynamic Programming Problems, the algorithm calculates shortest paths in a bottom-up manner. It first calculates the shortest distances which have at-most one edge in the path. Then, it calculates the shortest paths with at-most 2 edges, and so on. After the i-th iteration of the outer loop, the shortest paths with at most i edges are calculated. There can be maximum |V| – 1 edges in any simple path, that is why the outer loop runs |v| – 1 times. The idea is, assuming that there is no negative weight cycle, if we have calculated shortest paths with at most i edges, then an iteration over all edges guarantees to give shortest path with at-most (i+1) edges