In recitation 6, slide 16 you mentioned we saw a linear algorithm for finding single source shortest paths in an acyclic graph. Can you remind what was this algorithm?
Date: 02 Feb 2015 20:44
Number of posts: 3
RSS: New posts
If Im not wrong it goes something like this : First do a Topological sort. Then you can go vertex by vertex and update the distance in the correct order.
Yup, what Roie wrote is right. You sort the vertices tolopogically, and then you go from "left" to "right", relaxing the edges.
I suggest you 1) prove that it is correct, and the complexity is linear (it shouldn't be too hard).
2) formulate the answer as a dynamic program.