Hi, Thank you very much. I've just tried to use your implementation but I've some problems. What version of BGA are you using? I'm using version 1_33_0 but I can locate boost/io/format/std/pair.hpp that you include in your k_shortest.hpp (line 20). Because it is very important for me an implementation of this algorithm, I'm ready to change BGL version if it is necessary. Thanks a lot, Maurizio Vladimir Prus ha scritto:

Hi Giulio,

...

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?

Hi, I'm afraid BGL does not have such a algorithm at the moment.

One though that comes to me is the use another algorithm (not present in BGL, either), for finding k shortest paths. You'll then be getting next shortest path until the lengths are all the same.

There are several algorithms for finding k shortest paths, one being http://citeseer.ist.psu.edu/jimenez94algorithm.html

My implementation can be found at http://zigzag.cs.msu.su/~ghost/k_shortest Look specifically at the k_shortest.hpp file.

Of course, no warranties. This worked for me and I did test it against independent implementation, but the only way to find it it works for you is to test.

- Volodya

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

Vladimir Prus ha scritto:

Hi Giulio,

My implementation can be found at http://zigzag.cs.msu.su/~ghost/k_shortest Look specifically at the k_shortest.hpp file.

Hi Vladimir, I'm using your implementation. I've modified it a little bit to fit with my problem and now I'm ok. Thanks a lot, Maurizio

Douglas Gregor wrote:

On Sep 16, 2005, at 2:37 AM, Vladimir Prus wrote:

...

...

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?

Hi, I'm afraid BGL does not have such a algorithm at the moment.

One though that comes to me is the use another algorithm (not present in BGL, either), for finding k shortest paths. You'll then be getting next shortest path until the lengths are all the same.

Or, one can use Dijkstra's shortest paths algorithm with a custom visitor that accumulates predecessors in its edge_relaxed/ edge_not_relaxed events.

Yes, probably. For a DAG, you can run Dijkstra, and then traverse the graph from the end (sink) vertex, passining only along the edges that give the min path length. OTOH, such algorithm still has to be written, and one should consider what to do with cycles and so on... - Volodya

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 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users