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 fr

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.)