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