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

Subject: [boost] [graph] Efficiency of index map in dijkstra_shortest_paths
From: Jan Hudec (bulb_at_[hidden])
Date: 2012-10-17 03:21:05

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?

Thanks
Jan

-- 
						 Jan 'Bulb' Hudec <bulb_at_[hidden]>