Boost logo

Boost Users :

Subject: [Boost-users] [Graph] How to do multi source shortest path
From: Leo Hidd (leohidd_at_[hidden])
Date: 2012-03-06 11:37:52

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?

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?)

thx for your time,


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