Hi, The following algorithm should do the trick: // predecessors is the predecessor map // destinationNode is the node you want to reach // sourceNode is the source of the graph int currentNode = destinationNode; int predecessorNode = 0; std::cerr << boost::format("--- PATH: %d <- ") % destinationNode; do { predecessorNode = predecessors[currentNode]; if (predecessorNode == currentNode) { // Unreachable nextHop = 0; std::cerr << "XXX" << std::endl; break; } else if (predecessorNode == sourceNode) { // Next hop found nextHop = currentNode; std::cerr << sourceNode << std::endl; break; } else { // One hop on the path currentNode = predecessorNode; std::cerr << boost::format("%d <- ") % currentNode; } } while (true); Hope it helps, Florian -----Message d'origine----- De : boost-users-bounces@lists.boost.org [mailto:boost-users-bounces@lists.boost.org]De la part de dwaem Envoyé : lundi 23 mars 2009 16:23 À : boost-users@lists.boost.org Objet : Re: [Boost-users] Dijkstra shortest path Steven Watanabe-4 wrote:
AMDG
dwaem wrote:
int weight[] = {1, 1, 2, 2, 3, 4, 3, 4, 5, 6, 7};
<snip>
it shows distances and parents: distance(A) = 0, parent(A) = C distance(B) = 0, parent(B) = A distance(C) = 0, parent(C) = C distance(D) = 0, parent(D) = C distance(E) = 0, parent(E) = C
which makes no sense.
You're not using the weight array anywhere, so you get the default weight of 0 for every edge.
In Christ, Steven Watanabe
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Yes this is my obviouse oversight. But now when I have founded shortest path from node A to node B. How to display full path from A to B, not only parent of the last node. -- View this message in context: http://www.nabble.com/Dijkstra-shortest-path-tp22626827p22662345.html Sent from the Boost - Users mailing list archive at Nabble.com. _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users