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

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2003-07-01 15:12:11

Throw an exception?

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo

----- Mensaje Original -----
De: Richard Jepps <yg-boost-users_at_[hidden]>
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_at_[hidden]> 
> 
> Your use of Yahoo! Groups is subject to 
> http://docs.yahoo.com/info/terms/ 
> 
> 
>