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

From: Richard Jepps (yg-boost-users_at_[hidden])
Date: 2003-07-02 15:48:25

Volodya,

> The difference here is between worst-case complexity, which is the same
> O(V+E) for both problems, and average/minimum complexity.

That's right - the worst case is that the target vertex is the last one
to be analysed because it is the furthest from the source vertex.

If the target vertex is quite near to the source vertex stopping early
represents a significant optimisation. In my application a high proportion
of the shortest path problems are like this.

> - decide how to change dijstra_shortest_path interface. Guess it better
> accept a single target vertex and create appropriate terminating functor
> internally.

This would be the easiest to understand from an API point of view, but it
does
involve either adding a new function or changing the API of the existing
function.

If there was a function call that told the algorithm to stop it would
be very easy to implement a visitor without changing the API at all.

It might also be possible to add the target vertex as a property to
extend the API in a way that is compatible with current single-source
clients.

> - implement this.

I'm probably not the best person to do this because my C++ is not that good,
and I would have to get my employer to agree not to claim the copyright.

I'll see what I can do.

> I can help with it, but unfortunately, have no time at the moment to
> implement it myself. I can provide you with the modified
> depth_first_search.hpp, if you'd like to see more details.

This would be very helpful. Is it OK for you to post it here?
If not, my e-mail address is richard-dot-jepps-at-bentley-dot-com
(sorry about the spam precautions).

Thanks for your help.

Richard