4 ms·

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

• teraflop 12y ago
  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.)
• lorenzhs 12y ago
  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!