Re: [Boost-users] Find all the shortest path from a graph

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2005-09-16 12:00:17

On 9/15/05, Giulio Veronesi <giulio_veronesi_at_[hidden]> wrote:
> Hi all,
> 
> I'd like to extract all possible shortest path from a source to a
> destination... not only one path. Please, could you help me to resolve
> this problem?
> 
> Thanks a lot in advance,
> Giulio

Hi Giulio,

There's no efficient way to solve this problem in general, 
since there can be exponentially many paths between 
two vertices even in sparse graphs. Consider the graph 
below:

x o---o---o---o---o---o---o
   |    |    |    |    |    |    |
   o---o---o---o---o---o---o y

and enumerate all the simple paths from x to y. Given any
simple path, there's a set of edges on the "top row" that are
used by that path. Conversely, given any set of edges on
the top row, there's a unique simple path from x to y using
those edges. So there are 2^6 simple paths from x to y.
This construction can be generalized to create a graph with
2n vertices and 2^(n-1) simple paths between the "top left"
and "bottom right" vertices for any n >= 1. You can easily
come up with examples where there are exponentially many
shortest paths between two vertices, as well.

I'm assuming, since you didn't say, that you want to do this 
for unweighted graphs? If this is still what you want to do, I'd 
suggest running breadth_first_search on the graph to figure out 
the length of the shortest path between x and y. For the sake of 
discussion, let's say this length is 10 (10 edges, so the path 
consists of x, then 9 vertices, then y). Next, form a sequence of 
sets X0, X1, X2, ..., X9, where X0 = {x} and Xi for i > 0 is defined
as the set of all vertices adjacent to a vertex in X(i-1). Next, form 
a sequence of sets Y10, Y9, ..., Y1, where Y10 = {y} and Yi for
i < 10 consists of all vertices adjacent to a vertex in Y(i+1).
Finally, compute the intersection of Xi and Yi and store it in a
new set Vi for i = 1..9. Verify for yourself that the Vi's now have
two nice properties:

(1) Any sequence of vertices v1,v2,...,v9 where vi is in Vi for all i
     forms a path of length 10 between x and y
(2) No vertex occurs in more than one of the Vi's, so the sequences
     in (1) are actually simple paths. (You can verify this by assuming
     that some vertex u occurs twice, finding the minimum i such that u 
     is in Vi and the maximum i such that u is in Vi, and using this
     information to construct a path between x and y of length less than
     10, a contradiction)

Now, iterate through all such sequences and you have all shortest
paths between x and y. All the operations described above are easy
to do with BGL adjacency iterators and std::sets.

Aaron