|
Boost Users : |
From: Vladimir Prus (ghost_at_[hidden])
Date: 2005-09-16 02:37:41
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 list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net