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

13 Mar 2012

      On Tue, 13 Mar 2012, Leo Hidd wrote:
...
Le 09/03/2012 19:04, Jeremiah Willcock a écrit :
...
On Fri, 9 Mar 2012, Leo Hidd wrote:
...
...
...
An additional question, is there a way to modify the target or the 
source vertex of an edge? It would be useful to me because I run several 
iterations of MSSP with a different set of sources for each iteration 
(but the number of the sources is the same). Modifying the source/targe 
of an edge would avoid delete/re-add the zero-weight edges.
No, there isn't.  A direct implementation of MSSP will solve your 
problem, though, and I am working on one.  It will probably be committed 
to the Boost trunk next week.
wow, nice, thank you sir! Do you plan to also implement the 
distributed/parallel version of it, like for the 
delta_stepping_shortest_paths()?
I was planning on just doing the sequential version.
-- Jeremiah Willcock
it would be so nice to have the distributed MSSP, but I ignore how time 
consuming it would be to implement it in boost. A priori it should be as 
difficult (or easy) as for single source. Please let me know if you consider 
to implement distributed MSSP.
A version like you are asking about (starting from all of them in parallel 
and finding the closest to each vertex) is only a small change to the 
interface to SSSP; it is for the sequential code, too.  Here are what are 
probably the only changes to need to be made (in 
 in the Boost 
trunk):

1. Add a new version of delta_stepping_impl::run that takes a range of 
vertices, and processes each of them like it does to s right now (set 
distances to 0 on local ones and put them into buckets).

2. Add a new version of delta_stepping_shortest_paths that takes an 
iterator range of sources and calls the new impl function instead of the 
single-source version.

-- Jeremiah Willcock