
Boost Users : 
From: Vladimir Prus (ygboostusers_at_[hidden])
Date: 20030702 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 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 you're reasoning is correct, but I've did not though a lot about it.
The difference here is between worstcase 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 outedges 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
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