Boost logo

Boost :

From: Rich Lee (llee1_at_[hidden])
Date: 2001-01-03 11:08:46

If your graph has weight on edges, there is no easy way you can stop in
the middle of Dijkstra's algorithm. -- You have to check whether all
in-edges of the destination vertex are processed or not. If all are done,
you could stop processing, otherwise, stopping processing may fail to find
the shorest-path. (The shorest-path may have more vertices than another

If your graph has the equal weight, you might already know that using BFS
to find the shortest-path is faster than Dijkstra's algorithm. In this
case, you can stop the algorithm right after you reach the vertex.

Lie-Quan Lee
University of Notre Dame

On Tue, 2 Jan 2001, Jeremy Siek wrote:

> 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: (+61 8) 8338 9222
> andrew> Fax : (+61 8) 8338 9229
> andrew> Email: andrew_at_[hidden]
> andrew>
> andrew>
> andrew>
> andrew>
> ----------------------------------------------------------------------
> 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