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] http://www.isite3d.com.au
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk