Re: [boost] Graph/Shortest Path usage question

From: Lie-Quan Lee (llee1_at_[hidden])
Date: 2001-01-04 00:41:06

On Wed, 3 Jan 2001, Dietmar Kuehl wrote:

> Rich Lee wrote:
>
> > 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.
>
> This discussion is off-topic for the Boost mailing list but I want to clarify
> what is being discussed: Dijkstra's algorithm maintains a priority queue of
> distances to nodes from the root. The distances are computed by adding
> the length of an edge to the distance of a finally labeled node. At any time
> there is a front of nodes from labeled nodes (those, whose distance from
> the root has determined; initially this is just the root) and the algorithm
> chooses the node with the minimum distance. This node is, at this point (not
> later) labeled with the distance from the root. At this point, the algorithm
> can stop processing if the shortest path from the root to the node is sought.
> Of course, this is not the time when the node is seen by the algorithm the
> first time: The distance may be updated when a shorter path is found. This
> is the reason why the Dijkstra algorithm needs a more powerful priority
> queue than the standard one. Well, this is only true if the textbook approach
> to Dijkstra's algorithm is used, ie. if nodes are stored in the priority queue;
> it is also possible to store edges and just discard edges leading to already
> labeled nodes. Due to the additional overhead for decreasing keys of nodes
> in a priority queue, this is probably more efficient, at least with relatively
> sparse graphs.
>
> If the algorithm supports an event for finally labeling a node (as any
> Dijkstra implementation should do), this is the point where the executation
> of the algorithm can be aborted.

I am sorry that I was wrong. The point Dietmar made above is absolutely
right.

-- 
Rich