
Boost : 
From: David Abrahams (abrahams_at_[hidden])
Date: 20010103 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
> inedges of the destination vertex are processed or not. If all are done,
> you could stop processing, otherwise, stopping processing may fail to find
> the shorestpath. (The shorestpath may have more vertices than another
> path.)
Am I missing something important? AFAIK, Dijkstra's algorithm is also called
bestfirst 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk