Re: [BGL] dijkstra_shortest_paths and the single-pair problem

From: David Abrahams (dave_at_[hidden])
Date: 2003-07-03 18:07:36

"Richard Jepps" <yg-boost-users_at_[hidden]> writes:

> I think that the termination criterion is quite straightforward using a
> DijkstraVisitor - it is when vis.finish_vertex(u, g) is called and u ==
> destination_node. Unfortunately I can't see how to stop the algorithm in a
> reasonable way.
>
> An unreasonable solution is to provide a custom graph and turn off all its
> edges when the termination criterion is met.
> This is unreasonable because the responsibility for termination belongs to
> the algorithm, not the data structure - I shouldn't have to modify the data
> structure to terminate the algorithm.
> It's also unreasonable because I have to customise both the graph and the
> algorithm to do something very simple.
>
> Is there a better way?

The best (and most efficient) way to terminate graph algorithms early
is by throwing an exception.  That's the intended way to use the
library, and it is documented that way in the FAQ.  The alternative
would be to have every visitor explicitly checking for termination at
every step, which would impose a high efficiency burden for large
problems.

HTH,
-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com