News for hackers. Stuff that matters.
Re:On Dijkstra's Algorithm by kelukelugames on Tuesday April 21, 2015 @12:33PM (#9415206)
This is a very dumb question. I understand how to implement Dijkstra's Algorithm. But if I want to get from point A to point B then how do I find the exact path?

I have to do some processing after running the algorithm, right?

Re:On Dijkstra's Algorithm by teraflop on Tuesday April 21, 2015 @01:22PM (#9415548)
Dijkstra's has the property that it computes the cost from A to every node that is closer to A than B is. (For this reason, the distance ordering of vertices from a starting point is sometimes called their Dijkstra rank.) You can use this to backtrack and compute the actual path.

Let d(x,y) be the single-edge distance between two adjacent nodes, and S(A,y) be the computed shortest path. If S(A,C) + d(C,B) == S(A,B), then any shortest path from A-C is also part of a minimal path from A-B. Starting from B, you can check all its neighbors to find one that is a predecessor on a shortest path, and then just repeat that process until you get back to the starting point.

(If you look at other dynamic programming problems, like longest common subsequence, they often use similar tricks to reconstruct a solution after the initial computation is done.)

Re:On Dijkstra's Algorithm by lorenzhs on Wednesday April 22, 2015 @07:06AM (#9419558)
During relaxation (if you found a new, shorter path to a node), you don't just update the cost of getting there, but also save how you got there (i.e., from which node). Then it's just a matter of retracing the steps from B to A!