Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk