David,
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.
Thanks for pointing this out - for future readers the link is: http://www.boost.org/libs/graph/doc/faq.html It is also worth noting that http://www.boost.org/libs/graph/doc/table_of_contents.html links to a lot of information that isn't in the BGL book.
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.
The algorithm already checks for termination for each node it deals with (if Q is empty in BFS), so the performance penalty would be very small. It might even be possible to define the test at compile time so that there was no performance penalty unless you explicitly ask for the check. The main problem with using an exception is that the solution to the single-source problem is a single function call, the solution to the single-pair problem is to implement a visitor using an exception - which would not be obvious to many Boost users (the developers are in a different league). It's as if the function has been made deliberately hard to use for half its potential users. Thanks for your reply, and sorry for asking a question that's been asked before. I did look, but I didn't find. Richard