# Boost Users :

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]

>
>

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
```