shortest paths algorithm - why backtrack from the end node instead of starting from the starting node? 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.
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.