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-09 12:08:09

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

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.