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

Subject: Re: [Boost-users] [Graph] How to do multi source shortest path
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-03-06 11:45:46

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