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

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

Le 06/03/2012 17:45, Jeremiah Willcock a écrit :
> 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.
>
do you think it could be implemented in a (near?) future version of 
Boost, so that SSSP would be a particular case of MSSP when only one 
source is given in the input parameters? It would really be nice. As for 
me to implement it myself, I fear I don't have enough skills to get into 
the code and make those changes properly.
>> 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.
y, true my bad xD
>
> -- Jeremiah Willcock
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users