On Tue, 6 Mar 2012, Leo Hidd wrote:
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?
It looks like that functionality is missing; to do it, you'd need a multi-source version of breadth_first_visit as well as one for dijkstra_shortest_paths{,_no_init}. It would not be hard to implement most likely, but it would preferably mean refactoring some of the existing single-source code to take a queue and use all elements initially in it.
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?)
You'd need a 16*10^12 element table, so that is impractical. -- Jeremiah Willcock