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.
When you find the path from A to B do you abort the algorithm once it settles on the distance to B or do you continue until all vertices have been reached?
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.
When you return to the Dijkstra results do you just want to read the existing results or continue the Dijkstra algorithm where it was interrupted?
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?
Yes, that seems to be exactly what you need, provided you do not intend to resume the algorithm.
Thanks & Cheers!
You might be interested in a version of Dijkstra that can be interrupted and resumed: http://lists.boost.org/Archives/boost/2014/04/212891.php In that case you would need to cache the distance map, predecessor map, color map and priority queue. Best wishes, Alex