# 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?

To understand what this function is, take a look at the proof. The invariant is "after $$i$$ iterations, we've found all shortest paths of length at most $$i$$". 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))$$