Re: [Boost-users] Dijkstra shortest path

Subject: Re: [Boost-users] Dijkstra shortest path
From: Florian.PONROY_at_[hidden]
Date: 2009-03-23 11:33:53

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_at_[hidden]
[mailto:boost-users-bounces_at_[hidden]]De la part de dwaem
Envoyé : lundi 23 mars 2009 16:23
À : boost-users_at_[hidden]
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_at_[hidden]
> 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_at_[hidden]
http://lists.boost.org/mailman/listinfo.cgi/boost-users