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

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

On 9/17/05, Giulio Veronesi <giulio_veronesi_at_[hidden]> wrote:
> 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!). 

I said was that there are 2^6 simple paths from x to y. There are 7
shortest paths from x to y, each one being uniquely determined by
the vertical edge taken (if you use more than one vertical edge, you
can't get a simple path from x to y of length less than 9.) Again, my
example was just showing that there are sparse graphs with exponentially
many paths between two vertices; you can also come up with examples
where there are exponentially many shortest paths between two vertices
as well.

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

You're correct. So, add in a step at the end of the algorithm to check
to make sure that each sequence actually forms a path. 

Aaron