0
$\begingroup$

I was watching a dynamic programming video by Erik Demaine . He says here https://youtu.be/OQ5jsbhAv_M?t=2133 , finding the shortest paths from S to V for all V, by guessing the node after the starting node is not the right approach, and instead should guess the node before the last node. I didn't understand his explanation. Can someone explain better why find the path backwards? It seems to me that you should get the same answer either way and both approaches are equally good.

$\endgroup$
0
$\begingroup$

You want to find the shortest paths $S(s,v)$ to all nodes $v$ (31:30 in the video). In other words, we are interested in computing a function $f(v) = S(s,v)$, and, as explained in lecture, you can write it as $f(v) = \min_{(u,v) \in E} f(u) + w(u,v)$. In the end, it allows you to compute all such values in one go.

If you instead consider an equation $S(s,v) = \min_{(s,u) \in E} w(s,u) + S(u,v)$, you do can find $S(s,v)$ this way. However, you won't be able to find $S(s,u)$ for all other $u$ in the process, and you'll have to run the same algorithm again for other end vertices.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you. I missed the part about all V. I get it now. Since we are changing the v, we can reuse the S(s,u) computed the first time for all the remaining Vs, by starting from the end node. I can now put this question to rest and move on to next algorithm. $\endgroup$ – Suneel Jul 31 at 11:54
  • $\begingroup$ @ Suneel: Welcome to COMPUTERSCIENCE @SE. Can you please edit this point missed into the question? $\endgroup$ – greybeard Aug 1 at 6:04

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.