[BGL] dijkstra_shortest_paths and the single-pair problem

From: Richard Jepps (yg-boost-users_at_[hidden])
Date: 2003-07-01 08:00:52

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

Thanks

Richard