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

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