Throw an exception? Joaquín M López Muñoz Telefónica, Investigación y Desarrollo ----- Mensaje Original ----- De: Richard Jepps Fecha: Martes, Julio 1, 2003 3:00 pm Asunto: [Boost-Users] [BGL] dijkstra_shortest_paths and the single-pair problem

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

------------------------ Yahoo! Groups Sponsor -------------------- -~--> Get A Free Psychic Reading! Your Online Answer To Life's Important Questions.http://us.click.yahoo.com/Lj3uPC/Me7FAA/ySSFAA/EbFolB/TM ------------------------------------------------------------------- --~->

Info: <" target="l">http://www.boost.org> Wiki: <" target="l">http://www.crystalclearsoftware.com/cgi- bin/boost_wiki/wiki.pl>Unsubscribe: <')" >mailto:boost-users- unsubscribe@yahoogroups.com>

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/