Re: [boost] Graph/Shortest Path usage question

From: David Abrahams (abrahams_at_[hidden])
Date: 2001-01-03 23:43:55

----- Original Message -----
From: "Rich Lee" <llee1_at_[hidden]>

>
> If your graph has weight on edges, there is no easy way you can stop in
> the middle of Dijkstra's algorithm. -- You have to check whether all
> in-edges of the destination vertex are processed or not. If all are done,
> you could stop processing, otherwise, stopping processing may fail to find
> the shorest-path. (The shorest-path may have more vertices than another
> path.)

Am I missing something important? AFAIK, Dijkstra's algorithm is also called
best-first search, meaning that the least cost partial path is always
explored next, and if the edge weights are all positive, you will always
find the least cost path to any given node before you find any other path to
that node.

In other words, at least when I code Dijkstra's algorithm by hand, you know
the least cost path to a node the very first time you visit it.

-Dave