
Boost Users : 
From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 20030701 15:12:11
Throw an exception?
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
 Mensaje Original 
De: Richard Jepps <ygboostusers_at_[hidden]>
Fecha: Martes, Julio 1, 2003 3:00 pm
Asunto: [BoostUsers] [BGL] dijkstra_shortest_paths and the singlepair 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 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
> 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 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
>
>
>
>
>
>
>
>  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:boostusers
> unsubscribe_at_[hidden]>
>
> Your use of Yahoo! Groups is subject to
> http://docs.yahoo.com/info/terms/
>
>
>
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