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

From: Giulio Veronesi (giulio_veronesi_at_[hidden])
Date: 2005-09-17 01:58:53

Hi Aaron,

Thank you very much!

I tried to analyse your algorithm but I've one problem. Considering your 
example, you say that there are 2^6 shortest paths. I think, that the 
number of shortest paths is (6! + 1!). For istance, let us consider a 2x3.

0---1---2
|   |   |
3---4---5

We want all the shortest paths from 0 to 5.

Using your notation we have:
X0={0}, X1={1,3}, X2={0,2,4,6}
Y3={5}, Y2={2,4,8}, Y1={1,3,5,7}

Therefore:
V1 = X1 intersection Y1 = {1,3}
V2 = X2 intersection Y2 = {2,4}

Iterating through all the sequences we find the following paths:
0->1->2->5
0->1->4->5
0->3->4->5
0->3->2->5

But the last path is not a valid path. Is this correct or I've made a 
mistake?

Thanks so much,
Giulio

Aaron Windsor ha scritto:
> 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
> 
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>