3

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!

manuhalo
  • 165
  • 1
  • 8
  • I think [giogadi's answer](https://stackoverflow.com/a/15935735/7359123), while sensitive, is not conceptually clean. The approach I am leaning toward, to solve that same problem, is to first run an expensive johnson all pairs, then on edges of interest, get the actual detailed path with [this explanation on Dijsktra + predecessor map + post-parsing the map](https://stackoverflow.com/questions/12675619/boost-dijkstra-shortest-path-how-can-you-get-the-shortest-path-and-not-just-th?rq=1) ... [and a visitor exception to stop at destination vertex](https://stackoverflow.com/questions/32047840/make – AIDoubt May 24 '19 at 22:10

2 Answers2

2

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.

giogadi
  • 951
  • 1
  • 7
  • 20
0

Given the distance matrix, assuming there is a single shortest path for every (i,j) pair, you can easily reconstruct the path assuming the predecessor of w is u iif the potential of node w is equal to the potential of node u plus the cost or the uw edge.

baol
  • 4,362
  • 34
  • 44
  • Hi, thanks for the reply, unfortunately I cannot guarantee that there are not going to be multiple shortest paths with the same length. I decided to simply iterate the dijkstra algorithm over every source and be done with it. – manuhalo Jun 18 '12 at 09:45
  • Even when you have more than one shortest paths, finding a single shortest-path is trivial. – baol Jun 20 '12 at 21:29