[boost] Re: halting graph algorithms

From: Vladimir Prus (ghost_at_[hidden])
Date: 2003-09-10 00:23:30

Alexander Bertram wrote:

> Hi All,
>  
> I'm trying to use the dijkstra's shortest path algorithm in the context
> of a very large graph. I want to know if the shortest path from v to u
> is less than a particular distance. Because there are a great number of
> edges, I'd prefer that the algorithm exit once it is determined that
> there exists a path less than x, if even there exists a *shorter* path
> than x buried somewhere within the graph. Right now my visitor throws an
> exception which the call catches and ignores, but this doesn't seem very
> clean. Is there a better way to do this?

No, it's the only possible method (well, there's also setjump/longjump ;-),
but that's no-no in C++ code).

One other opinion is to make some visitor functions return bool. I believe
Jeremy is not happy about this idea and I also too have reservations about
it.

The first problem is that its interface change. Even if we can do it, it
means that some visitor function should return bool, even if it has never
need to terminate search at all.

Another possible problem is that performance may suffer. Personally, I don't
know if this is true. The algorithm has a lot of code already, and single
if statement might have negligible effect.

- Volodya