
Boost Users : 
From: Richard Jepps (ygboostusers_at_[hidden])
Date: 20030701 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 singlepair problem that are asymptotically
faster than the algorithms that solve the singlesource problem".
I think this is because the singlesource 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 singlesource problem can only be solved in infinite time, but the
singlepair 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
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net