On 5/14/14, 12:59pm, alex wrote:
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?
Right now, I just use boost::dijkstra_shortest_paths, specifying only one node (the source).
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?
The shortest path can be called ~1M times, and being quite a novice on boost, I don't know how to stop it, I am happy that I made boost::dijkstra_shortest_paths work! :)
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.
That's quite reasonable, an unorderd_map with the predecessor map seems to be a simple and effective solution. Thanks for the tips!