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

Subject: Re: [Boost-users] [Graph] Caching Dijkstra results
From: alex (alexhighviz_at_[hidden])
Date: 2014-05-14 06:59:53

>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