Boost logo

Boost Users :

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:
>> 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]

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at