
Boost : 
From: Rich Lee (llee1_at_[hidden])
Date: 20010103 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
inedges of the destination vertex are processed or not. If all are done,
you could stop processing, otherwise, stopping processing may fail to find
the shorestpath. (The shorestpath may have more vertices than another
path.)
If your graph has the equal weight, you might already know that using BFS
to find the shortestpath is faster than Dijkstra's algorithm. In this
case, you can stop the algorithm right after you reach the vertex.
Cheers,
LieQuan 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 ISiTE
> andrew> Senior Software Engineer 3D Laser Imaging
> andrew> Phone: (+61 8) 8338 9222
> andrew> Fax : (+61 8) 8338 9229
> 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: (219) 6313906
> 
>
>
>
>
>
>

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk