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.
1 Answer
$\begingroup$ $\endgroup$
2 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.
- $\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– Suneel2020-07-31 11:54:33 +00:00Commented Jul 31, 2020 at 11:54
- $\begingroup$ @ Suneel: Welcome to COMPUTERSCIENCE @SE. Can you please edit this point missed into the question? $\endgroup$greybeard– greybeard2020-08-01 06:04:18 +00:00Commented Aug 1, 2020 at 6:04