On Wed, May 14, 2014 at 11:14 AM, Sensei wrote:

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?

A simple way to do it would be to use an associative container with both source and destination as key, and the full path as value. I did this before (not with boost graph though) and it was enough for my case, but if you want smarter cache that might be more complicated.

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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users