Re: [boost] Graph/Shortest Path usage question

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
path.)

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.

Cheers,
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: [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]
> ----------------------------------------------------------------------
>
>
>
>
>
>

--