[Boost-users] [Graph] How to do multi source shortest path

Subject: [Boost-users] [Graph] How to do multi source shortest path
From: Leo Hidd (leohidd_at_[hidden])
Date: 2012-03-06 11:37:52

Hi all,

I have a graph and multiple sources (please read this thread: 
http://thread.gmane.org/gmane.comp.lib.boost.user/73084/focus=73086 
first paragraph, for the characteristics of the graph, if it matters). 
So, instead of running the single source shortest path (SSSP) algorithm 
(e.g., dijkstra_shortest_paths()) multiple times, what I do is that I 
specify several sources instead of only one (so all the sources are 
initialized with distance 0 and put into the queue) and than I run 
Dijkstra as one usually does for SSSP. Doing so, the multi source runs 
almost as fast as a single source instead of running 
NbOfSouces*ElapsedTimeForSingleSource. Then, I'd like to know if it's 
possible to use boost algorithms for multi-source shortest path, like 
specifying several sources or anything alike. And, in the case it is 
possible, it would be possible to have an array with the index of the 
source the closest to a given node?

All pairs is not a solution because the number of sources is way less 
than the number of nodes in the graph and because all sources use lots 
of memory for storing the distances (for a 4 million nodes graph I'd 
need a 4*10^12 elements table, don't?)

thx for your time,

leo