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

Subject: Re: [Boost-users] [Graph] How to do multi source shortest path
From: Gordon Woodhull (gordon_at_[hidden])
Date: 2012-03-07 00:53:46

On Mar 6, 2012, at 12:37 PM, Leo Hidd <leohidd_at_[hidden]> wrote:

> 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.

Why not just create a "super source" vertex with zero-weight edges to all the sources you want?

Cheers,
Gordon