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