Boost logo

Boost Users :

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

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