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

From: Vladimir Prus (yg-boost-users_at_[hidden])
Date: 2003-07-02 03:48:59

Richard Jepps wrote:

> I would like to use the dijkstra_shortest_paths algorithm to find the
> shortest path from one specified vertex to another.
> 
> The standard Boost implementation will find this, but it will continue
> until it has found the shortest paths to all nodes in the graph (i.e.
> solved the single source problem).
> 
> The BGL book (Section 5.1, pp76) says: "It turns out that there are no
> algorithms for solving the single-pair problem that are asymptotically
> faster than the algorithms that solve the single-source problem".
> I think this is because the single-source algorithms all have the property
> that it is possible to determine whether the shortest path to any given
> node has been found during the execution of the algorithm, therefore you
> can use the same algorithm to solve both types of problem provided that
> the termination criterion is appropriate to the problem.
> 
> Consider this problem: "find the shortest path from a source vertex u to a
> nearby destination vertex v in an infinitely large directed weighted graph
> G in finite time."
> The single-source problem can only be solved in infinite time, but the
> single-pair problem can be solved relatively quickly (because the two
> vertices are near each other).

I think you're reasoning is correct, but I've did not though a lot about it.
The difference here is between worst-case complexity, which is the same
O(V+E) for both problems, and average/minimum complexity.

> 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.

I happen to need something similiar --- prevent depth_first_visit from
traversing out-edges of certain vertices. I've implemented this using
functional object which is called when vertex is discovered and tells if the
vertex is terminating or not.

Something very similiar is possible for breadth_first_search, which is used
internally by Dijkstra. The remaining problems are:

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

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.

- Volodya