Bellman Ford Dynamic Programming I have been learning graph algorithms, and the concept of dynamic programming is quite succinct. However, I read that Bellman Ford is a form of dynamic programming. I am not sure why since given so many unnecessary re-computations, it is not exactly efficient in the likes of other dynamic programming that computes the sub-problems bottom up to the final problem. For example, FloyWarshall has a well defined sub structure of considering all other vertices up to k.
But for Bellman Ford, the implementation is not really relying on any computed sub problems, it is just a brute force algorithm that correctly returns the shortest path but it is not correctly computing the sub-problems in some correct order needed by a dynamic programming algorithm?
Dynamic programming doesn't necessarily mean that your solution will be efficient. It just means that your problem can be defined using a recursive function, for which you can use memoization.
To understand what this function is, take a look at the proof. The invariant is &quot;after $i$ iterations, we've found all shortest paths of length at most $i$&quot;. Therefore, we can define our function $f(v, \ell)$ - the length of the shortest path to vertex $v$ with length at most $\ell$ - in the following way:
$$f(v, \ell) = \min_{u \ \in\  in(v)} (f(u, \ell-1) + d(u,v))$$
What Bellman-Ford does is slightly different (e.g. it can compute all shortest paths in a single iteration, if our order is lucky), but it can only help us, so we don't mind.