Re: [boost] Graph/Shortest Path usage question

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

On Wed, 3 Jan 2001, Dietmar Kuehl wrote:

dietma> Rich Lee wrote:
dietma> 
dietma> > If your graph has weight on edges, there is no easy way you can stop in
dietma> > the middle of Dijkstra's algorithm. -- You have to check whether all
dietma> > in-edges of the destination vertex are processed or not.
dietma> 
dietma> This discussion is off-topic for the Boost mailing list
dietma> but I want to clarify

I see no reason why this is off-topic. It pertains to the correctness and
use of a BGL algorithm.

dietma> what is being discussed: Dijkstra's algorithm maintains a
dietma> priority queue of distances to nodes from the root. The
dietma> distances are computed by adding the length of an edge to
dietma> the distance of a finally labeled node. At any time there
dietma> is a front of nodes from labeled nodes (those, whose
dietma> distance from the root has determined; initially this is
dietma> just the root) and the algorithm chooses the node with the
dietma> minimum distance. This node is, at this point (not later)
dietma> labeled with the distance from the root. At this point,
dietma> the algorithm can stop processing if the shortest path
dietma> from the root to the node is sought. Of course, this is

This event point is the "on_discover" event in the BGL algorithm: the
point at which the node is removed from the priority queue (because it is
the node with minimum distance). In Andrew's early post he asked if the
"finish" event would work. It would work, though by that time a little
extra (unnecesary) processing has occurred, namely all the outgoing edges
have been added to the queue.

dietma> not the time when the node is seen by the algorithm the
dietma> first time: The distance may be updated when a shorter
dietma> path is found. This is the reason why the Dijkstra

The event point when a node is "seen" is the "examine_edge" event,
and as Dietmar points out, this event may occur several times for
the same target vertex before that vertex comes out of the priority
queue. 

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