all-pairs shortest path algorithm that actually saves routes?

Question

I'm trying to rewrite a simple network load simulation tool I created, this time using Boost libraries to improve performances (and avoid implementation mistakes). In the original program I computed shortest paths from every source node in the network by invoking Dijkstra's algorithm on it, so I was delighted when I found out that there's an all-pairs algorithm like the Johnson's one (my graphs are going to be relatively sparse, I assume). However that algorithm only returns a distance matrix, while I need the actual routes - at the very least something like the predecessor map that Dijkstra's algorithm implementation returns. Is there any way to achieve that or should I just go back to repeatedly invoking Dijkstra for each vertex in the graph? I've been looking around the whole day but couldn't find anything, guess I just wanted to be sure before I moved back to the iteration approach.

Thanks!

Answer 1

This is an old question, but I was looking for an answer to this too and I found the previous answer to be a bit vague.

Say you have the distance matrix, and you want to find the shortest path from vertex i to vertex j. Vertex i has a set of possible successors N; the successor to i is the vertex in N which minimizes:

c(i,n) + d(n,j)

where c(i,n) is the cost of the edge between i and neighbor n, and d(n,j) is the shortest distance between n and j given by the distance matrix. You simply pick the neighbor n which minimizes the above equation, then repeat the process, replacing i with n and N with the neighbors of n.