On 9/17/05, Giulio Veronesi
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