Re: [boost] [graph] Efficiency of index map in dijkstra_shortest_paths

Subject: Re: [boost] [graph] Efficiency of index map in dijkstra_shortest_paths
From: Alex Hagen-Zanker (ahh34_at_[hidden])
Date: 2012-10-17 08:32:21

On Oct 17 2012, Jan Hudec wrote:

>Hello,
>
> The dijkstra_shortest_paths function requires an index map that maps 
> vertices to index in range [0, num_vertices(g)). However there are 
> several practially important algorithms that requite calculating shortest 
> path trees with many times from each vertex, but each tree only spanning 
> small fraction of an otherwise huge graph.
>
> I am somewhat concerned about allocating arrays of the size of the graph 
> (that has millions of vertices) over and over (hundred million or more 
> times) when many scans will stop after hundreds of vertices. Note that 
> filtering the graph is not an option, because the stopping condition is 
> given by radius or number of scanned vertices, but you obviously don't 
> know which vertices will be scanned.
>
>Is there an option to use associative container for the queue indices? Or
>would it be useful to add it?
>
>
One strategy that you could follow is to allocate the arrays only once and 
after each application of the shortest path algorithm only re-initialize 
the vertices that have been changed. You could for instance make use of a 
visitor that keeps a list of all discovered vertices.

To apply the dijkstra_shortest_path without initialization, use the 
dijkstra_shortest_paths_no_init function.

Best wishes, Alex