Hi Volodya,
thanks for this solution [k_shortest.hpp]. It compiles and works for the
files given (with minor changes - commenting out the io::<< declaration and
some cout statements).
However, when I use bundledProps for vectices and edges, I get compilation
errors.
So, for instance
if the graph definition used is the following, instead of the one you have in
the example k_shortest_test.cpp, then the compilation fails.
struct CCRVertexProps
{
std::string vertex_name; // name of CCR
int tmp; // could be anything
};
struct CCREdgeProps
{
string name; // edgename
int edge_weight_t;
};
typedef boost::adjacency_list
From boost archives:
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
------------------------------------------------------------------------------------------------------
------------------------------------------begin------------------------------------------------------
k_shortest.hpp: In member function
`boost::Shortest_paths_finder<G>::Path_set::heap_type*
boost::Shortest_paths_finder<G>::initialize_heap(boost::graph_traits<G>::vertex_descriptor)
[with G = boost::adjacency_list