2
$\begingroup$

We recently learned Bellman-Ford algorithm for shortest path in class, but I didn't understand it. Can you give me intuition for why the algorithm works? And can you please explain why it is correct? Why are we sure to find negative circles?

Also, we learned the following two lemmas:

Lemma (upper bound property): At all times we have that for all $v$, $v.d \ge \delta(s,v)$.

Lemma (Path-relaxation property): Let $p = \langle s=v_1, v_2, \ldots, v_n \rangle$. Following any sequence of relaxations in which the edges $(v_1,v_2),(v_2,v_3),\ldots,(v_{k-1},v_k)$ are relaxed in order, we have that $v_k.d \le w(p)$.

Here:

  • $v.d$ is the distance of $v$ from the initial vertex $s$. (We constantly update this value using the relax function in the Bellman–Ford algorithm.)

  • $\delta(s,v)$ is the minimum weight path between $s$ and $v$.

  • $w(p)$ is the total weight of path $p$.

Can you give me an intuition for the lemmas and what they mean?

$\endgroup$
2
  • $\begingroup$ What is "$v.d$"? What is "$s.v$"? What is "$\delta(s.v)$"? What is "$w(p)$"? $\endgroup$ Apr 20 at 8:45
  • $\begingroup$ edited, now its more clear ? $\endgroup$
    – user14732
    Apr 20 at 9:25
2
$\begingroup$

I can give you the intuition behind Bellman-Ford. It is beautiful! I'm going to do it in an indirect way. I want to share a warm-up puzzle that might seem unrelated, but stay with me.

Suppose we have a digital door lock with a four-digit code (each digit is 0..9), with a funny property: you can enter in extra stuff between the digits of the code and the lock will still open up. For instance, if the code was 2749, then you could enter in 32675049, and the lock would open up, because 32675049 contains 2749 as a subsequence.

Challenge: what is the shortest sequence you can come up with, that will guarantee to open the lock? You could of course enter in each of the $10^4$ possible codes one by one, but that would require you to enter 40,000 digits; can you find a faster way?

Go ahead, see if you can solve it on your own.

Hint:

Whatever the secret code is, we need it to appear as a subsequence of your chosen sequence. If we start with 0123456789, we are guaranteed to get at last one digit into the code. Can you take it from there?

Hint:

You should be able to find a sequence of length 40 that suffices.

Really, I want you to solve it yourself! It'll be rewarding and help you understand Bellman-Ford.


Now back to Bellman-Ford. Let's consider a graph with no negative cycles, but where edge distances can be positive or negative. The relax operation has an interesting property:

  • Suppose the shortest path from $s=v_1$ to $v_n$ is via the path $v_1 \to v_2 \to \cdots \to v_{n-1} \to v_n$. If we do some sequence of relax operations, that includes Relax($v_1,v_2$), Relax($v_2,v_3$), ..., Relax($v_{n-1},v_n$) as a subsequence, then $d[v_n]$ will hold the correct distance from $s$ to $v_n$.

In other words, this refers to a sequence of relax operations where we do some relaxes, then Relax($v_1,v_2$), then relax on some other edges, then Relax($v_2,v_3$), then relax on some more edges, and so on. The property holds no matter what other relax operations you do in the middle -- you can add as many extra relax operations in the middle anywhere you want and they won't do any harm.

Moreover, once $d[v_n]$ gets set to the correct value, it stays correct forever.

So if our goal is to come up with the correct distance in $d[v_n]$, we can think of that as a digital door lock like the one above: there is some secret code (the code is a sequence of edges, namely, $(v_1,v_2),\dots,(v_{n-1},v_n)$) that is not known to us, but if we do a sequence of relax operations on some sequence of edges, and if the secret code appears as a subsequence in there, then the lock will open (i.e.,, $d[v_n]$ will get set to the correct distance), and will stay open forever after (i.e., $d[v_n]$ will hold the correct value from there on).

So this is just like the digital door lock puzzle above! The challenge is to construct a sequence of edges, so that if we relax edges in that sequence, it'll surely include the code (the shortest path) as a subsequence. Now you can verify that the sequence of edge relaxations done by Bellman-Ford exactly matches the solution to the digital door lock puzzle above.

I'll let you prove the property I mentioned above. It follows from the two lemmas you quoted.

$\endgroup$
0
$\begingroup$

The first lemma states that $v.d$ is always an upper bound on the distance from $s$ to $v$.

The second lemma states that $v.d$ becomes equal to the distance form $s$ to $v$ if we relax edges $e_1,\ldots,e_\ell$ which together form a path of minimal weight from $s$ to $v$.

Put together, the lemmas imply that the Bellman–Ford algorithm computes shortest paths correctly:

  • The first lemma guarantees that $v.d$ is always at least $\delta(s,v)$.

  • The second lemma guarantees that $v.d = \delta(s,v)$ after $\ell$ rounds, where $\ell$ is the length of a minimum weight path from $s$ to $v$.

$\endgroup$
2
  • $\begingroup$ can you give an intuition for how and why algorithm work? $\endgroup$
    – user14732
    Apr 20 at 14:09
  • $\begingroup$ It’s beyond me. Perhaps Khan Academy has a video on that? $\endgroup$ Apr 20 at 14:17

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.