1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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 "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))$$

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.

$\endgroup$
1
  • $\begingroup$ Oh now I see what people mean when they say the intuition of the dynamic programming of Bellman Ford. thanks! $\endgroup$ – Ken Gondor Jul 28 '20 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.