Re: [boost] Graph/Shortest Path usage question

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-01-02 11:01:56

This is currently no straightforward way to stop early with the BGL
dijkstra algorithm. As Dietmar mentioned, this would be easier with an
algorithm iterator approach, but we don't have that yet (so little time,
so much stuff to do). Also, we could change the BFS family of algorithms
to explicitly allow for an early stop. I'll try to look into this...
perhaps you could also take a look into what changes would need to be
made.

The exception throwing would probably work, though I'd only want
that to be a temporary solution...

Cheers,
Jeremy

On Tue, 2 Jan 2001, Andrew Myers wrote:

andrew> I want to use the graph library to determine the shortest path between two
andrew> vertices in a graph.
andrew> 
andrew> I can use the Dijkstra algorithm to solve the single
andrew> source problem and get the answer I need. However in my
andrew> application it is likely that the two vertices selected
andrew> are close together anyway - there will only be a few
andrew> vertices making up the shortest path in relation to the
andrew> entire vertex set.
andrew> 
andrew> So I want to know how to terminate the algorithm once the
andrew> destination vertex is reached, seeing as it will not be
andrew> necessary to solve the shortest path to each vertex in my
andrew> graph.
andrew> 
andrew> I was thinking of using on_finish_vertex in the
andrew> uniform_cost_search visitor. By my understanding, once a
andrew> vertex is added to the shortest path tree, then there will
andrew> be no subsequent shorter paths to that vertex existing.
andrew> How can I use the visitor to terminate the algorithm? Is
andrew> throwing an exception the way to go?
andrew> 
andrew> Any comments gratefully accepted.
andrew> 
andrew> Regards.
andrew> 
andrew> -- 
andrew>   Andrew Myers                                                      I-SiTE 
andrew>   Senior Software Engineer                                3D Laser Imaging
andrew>   Phone: [phone]                  
andrew>   Fax  : [phone]                         
andrew>   Email: andrew_at_[hidden]                   http://www.isite3d.com.au
andrew> 
andrew> 
andrew> 
andrew> 

----------------------------------------------------------------------
 Jeremy Siek                        www: http://www.lsc.nd.edu/~jsiek/
 Ph.D. Candidate                  email: jsiek_at_[hidden]
 Univ. of Notre Dame         work phone: [phone]
----------------------------------------------------------------------