Boost logo

Boost :

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

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


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> 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> 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> 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> Any comments gratefully accepted.
andrew> Regards.
andrew> --
andrew> Andrew Myers I-SiTE
andrew> Senior Software Engineer 3D Laser Imaging
andrew> Phone: (+61 8) 8338 9222
andrew> Fax : (+61 8) 8338 9229
andrew> Email: andrew_at_[hidden]

 Jeremy Siek www:
 Ph.D. Candidate email: jsiek_at_[hidden]
 Univ. of Notre Dame work phone: (219) 631-3906

Boost list run by bdawes at, gregod at, cpdaniel at, john at