[Boost-users] graph- single source K shortest path with Boost Library

Subject: [Boost-users] graph- single source K shortest path with Boost Library
From: Alexandre Lima (alexandre.dll_at_[hidden])
Date: 2011-01-31 05:10:35

Hi,

I would like to know if somebody could help me with Graphs. I need to find
the 10th or kth shortest path in a single source problem, weighted >0, in
other words, I need to keep the 10th or more first paths of one source to
all other vertexes. I had already done that using a K shortest path
algorithm (Yen, http://code.google.com/p/k-shortest-paths/ ),which discovery
all the paths of a source to a sink, and I had just used a "for" with an
objective to try all the sink nodes to solve the problems to all vertexes.
It works, but the problem is that I can't use it in a big graph with 500 000
nodes, problems with memory. And now I am trying to use the boost library to
compute  at least the 10th shortest path to all nodes from a sink, but I
don't know how can I keep the other paths. Attached: graph_al.cpp that is
the code of boost library to compute a single source shortest path with
dijkstra and pseudo_code that I was thinking to use to storage the other
paths, but I don't know how to use it in a complex code like dijkstra boost
code. If someone could help me ?

thank you in advance.

Alexandre de Lima