Boost logo

Boost :

From: Andrew Myers (andrew_at_[hidden])
Date: 2001-01-02 01:57:49

I want to use the graph library to determine the shortest path between two
vertices in a graph.

I can use the Dijkstra algorithm to solve the single source problem and get the
answer I need. However in my application it is likely that the two vertices
selected are close together anyway - there will only be a few vertices making up
the shortest path in relation to the entire vertex set.

So I want to know how to terminate the algorithm once the destination vertex is
reached, seeing as it will not be necessary to solve the shortest path to each
vertex in my graph.

I was thinking of using on_finish_vertex in the uniform_cost_search visitor. By
my understanding, once a vertex is added to the shortest path tree, then there
will be no subsequent shorter paths to that vertex existing. How can I use the
visitor to terminate the algorithm? Is throwing an exception the way to go?

Any comments gratefully accepted.


  Andrew Myers                                                      I-SiTE 
  Senior Software Engineer                                3D Laser Imaging
  Phone: (+61 8) 8338 9222                  
  Fax  : (+61 8) 8338 9229                         
  Email: andrew_at_[hidden]         

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