Re: [boost] Graph/Shortest Path usage question

From: Dietmar Kuehl (dietmar_kuehl_at_[hidden])
Date: 2001-01-03 12:52:21

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.