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

Subject: Re: [Boost-users] [Graph] Caching Dijkstra results
From: Sensei (senseiwa_at_[hidden])
Date: 2014-05-14 07:11:17

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!