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-09 12:17:16

On Fri, 9 Mar 2012, Leo Hidd wrote:

>
>>> and how do I create this "super source" vertex? The 
>>> dijkstra_shortest_paths function takes only one vertex_descriptor, not an 
>>> array of it (isn't it?).
>> I meant, just add a special vertex to your graph and connect it with 
>> zero-weight edges to all the sources you want, and specify that as the 
>> source. Requires a little bit of detective work at the end to see which 
>> source a path goes through, but it should get you your answer.
>> 
>> Cheers,
>> Gordon
>> 
> thx Gordon, the extra vertex and additional zero-weight edges do the job just 
> fine ;)
>
> However, it would be nice to avoid the Sherlock Holmes part of the job. In my 
> case, I actually don't need the path as long as I have the index of the 
> closest source. For a small number of sources, the source search through the 
> path for all nodes takes a non negligible time compared to the MSSP search:
>
> example with 3 million nodes, 9 million edges (undirected graph, 
> dijkstra_shortest_paths_no_color_map)
> 0- 1     source: SSSP 4800ms
> 1- 60    sources: MSSP 6309 ms, source search 1778 ms
> 2- 600   sources: MSSP 7494 ms, source search  634 ms
> 3- 6000  sources: MSSP 8408 ms, source search 289 ms
> 4- 60000 sources: MSSP 9292 ms, source search 130 ms
> (of coarse, more sources you have, smaller will be the average path, thus the 
> source search)
>
> So it would be nice if there was a way to return a table with the index of 
> the closest source for each node (i.e., the source to which the distance_map 
> corresponds). The additional MSSP run-time to keep track of the closest 
> source would be negligible.

That can be done with a visitor: have closest_source as a property map, 
then on each edge_relaxed event, copy the closest source property from the 
edge's source to its target.

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

-- Jeremiah Willcock