Re: [Boost-users] [Graph] Caching Dijkstra results

Subject: Re: [Boost-users] [Graph] Caching Dijkstra results
From: Arne Vogel (avogel_at_[hidden])
Date: 2014-05-14 05:51:07

Hi Sensei,

I haven't used BGL's dijkstra_shortest_paths, which I assume you are 
referring to, but I have some experience with Dijkstra's algorithm. As 
far as I understand dijkstra_shortest_paths, all that you have to do is 
store the PredecessorMap after the algorithm has finished. This will 
provide you with a map version of the spanning tree (a tree whose root 
is the start vertex and whose edges are all on shortest paths). 
(Strictly speaking, the spanning tree need not be unique if you consider 
ECMP = equal cost multipath, but it seems dijkstra_shortest_paths 
doesn't support that anyway.)

To read the path from the PredecessorMap, you work your way backwards 
from the destination vertex to the source vertex, always looking up the 
predecessor of the current vertex in the predecessor map, until the 
current vertex is equal to the source vertex. Then you just reverse the 
path if necessary. Or, as simplified code:

vector<vertex> path;
for ( vertex current = destination; current != source; current = 
predecessor[current] )
{
     path.push_back(current);
}
path.push_back(source);
std::reverse(path.begin(), path.end());

You'll need to store a separate predecessor map for each source vertex, 
of course.

Hope that helps,
Arne Vogel

On 14.05.2014 11:14, Sensei wrote:
> Dear all,
>
> I need to find the shortest path from a node to another, and this 
> operation will be performed several times with different 
> source/destination nodes. In many cases, I would need the same source, 
> so I was thinking about caching the results from Dijkstra.
>
> Sincerely, I don't know what I should cache. My initial thought is 
> creating a hashmap with key being the source node, and value something 
> that allows me to easily retrieve the path.
>
> What do you think I need to cache? Does it suffices to have a map from 
> node index (std::size_t) to the node's predecessor map?
>
> Thanks & Cheers!
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users