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-06 11:45:46

On Tue, 6 Mar 2012, Leo Hidd wrote:

> Hi all,
> I have a graph and multiple sources (please read this thread:
> first
> paragraph, for the characteristics of the graph, if it matters). So, instead
> of running the single source shortest path (SSSP) algorithm (e.g.,
> dijkstra_shortest_paths()) multiple times, what I do is that I specify
> several sources instead of only one (so all the sources are initialized with
> distance 0 and put into the queue) and than I run Dijkstra as one usually
> does for SSSP. Doing so, the multi source runs almost as fast as a single
> source instead of running NbOfSouces*ElapsedTimeForSingleSource. Then, I'd
> like to know if it's possible to use boost algorithms for multi-source
> shortest path, like specifying several sources or anything alike. And, in the
> case it is possible, it would be possible to have an array with the index of
> the source the closest to a given node?

It looks like that functionality is missing; to do it, you'd need a
multi-source version of breadth_first_visit as well as one for
dijkstra_shortest_paths{,_no_init}. It would not be hard to implement
most likely, but it would preferably mean refactoring some of the existing
single-source code to take a queue and use all elements initially in it.

> All pairs is not a solution because the number of sources is way less than
> the number of nodes in the graph and because all sources use lots of memory
> for storing the distances (for a 4 million nodes graph I'd need a 4*10^12
> elements table, don't?)

You'd need a 16*10^12 element table, so that is impractical.

-- Jeremiah Willcock

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