I am trying to understand the Bellman-Ford algorithm from Jon Kleinberg, Éva Tardos: *[Algorithm Design]. Page no: 296 The recursive equation that is written: $$M[v]= \min(M[v], \min_{w\in V} (c_{vw} + M[w]).$$

I am not getting how this equation is correct?
Because in the book it is written that $M[v]$ is the shortest path from $v-t$,
but shouldn't $M[v]$ be the shortest path from $s-v$ using at most $i-1$ edges?

  • $\begingroup$ Welcome to COMPUTER SCIENCE @SE. When something in a book seems off, restart reading at the start of the paragraph, sub-chapter or chapter. In 6.8 Shortest Paths in a Graph, there's a note starting Let’s use OPT(i, v) to denote the minimum… following the first proof. Also, look at the "dynamic programming table in (b)" two pages before the formula. $\endgroup$ – greybeard Oct 24 '20 at 6:58
  • $\begingroup$ (While you're at it: I seem to have missed a closing parenthesis, and there is one "italics star" left from removing the URL.) $\endgroup$ – greybeard Oct 25 '20 at 16:56
  • $\begingroup$ Yeah, because you told something about copyright, and I didn't knew If I had right to add link or not. So I removed the link $\endgroup$ – Dhruvil Amin Oct 25 '20 at 17:04

Your Answer

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

Browse other questions tagged or ask your own question.