Re: [boost] Graph/Shortest Path usage question

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-01-04 12:18:14

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

In the AI world, Dijkstra's corresponds to a uniform cost search. From
what I've read this is a bit different from a best-first search in that a
best-first search also uses a heuristic function as a guide in choosing
which way to explore.

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

Right, as long as by "visit" you mean when the node is removed from
the queue: the "discover" event in BGL.

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                        www: http://www.lsc.nd.edu/~jsiek/
 Ph.D. Candidate                  email: jsiek_at_[hidden]
 Univ. of Notre Dame         work phone: [phone]
----------------------------------------------------------------------