Re: [boost] Graph/Shortest Path usage question

From: Dietmar Kuehl (dietmar_kuehl_at_[hidden])
Date: 2001-01-02 08:36:24

Hi,
Andrew Myers wrote:

> So I want to know how to terminate the algorithm once the destination vertex is
> reached, seeing as it will not be necessary to solve the shortest path to each
> vertex in my graph.

This is not an answer to your question but just comment because the concepts
of algorithm implementation are an area I'm quite interested in: This is exactly
why I'm a strong proponent of "algorithm iterators"! With these, the loop of the
algorithm is extracted from the actual algorithm giving lots of control to the user

of the algorithm. Rather than providing a visitor object to deal with the events
in the algorithm, the user basically just asks the algorithm object for the next
event. Algorithm termination is in this case obviously trivial (however, I guess
that this also applies to the visitor approach although I don't know the details).
There are also other things which are trivial, eg. running two instances of the
algorithm pseudo-paralell. This can be useful eg. in the shortest path context
to search from two starting points creating two growing bubbles until they
touch: Depending on the connectivity of the nodes this can be heuristically
faster than searching from just one node (not a proof but what might possibly
be turned into one: If the nodes are distributed in the 3D, or even higher
dimensional, space and the distances between the nodes are the length of the
edges, then the number of nodes investigated grows cubic with diameter of
the bubble; using two bubbles simply reduces the diameters of the two
bubbles and hence the number of the nodes).

The major drawbacks of this approach are increased complexity of the
algorithm implementation and, at least potentially, an impact on the
performance. Personally, I think that the provided flexibility is simply
necessary.