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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Oh now I see what people mean when they say the intuition of the dynamic programming of Bellman Ford. thanks! $\endgroup$ Commented Jul 28, 2020 at 9:05

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.