On Wed, 12 May 2010, Eric Fowler wrote:
I noticed the Boost doc for dijkstra_shortest_paths() says that the algorithm terminates when the priority queue is empty, which implies visiting every vertex, which is not necessary to find the shortest path between two vertices. I would like to use the algorithm to find the shortest path to a known vertex, which means stopping it before the queue is empty. At what point can I (the library client) decide to end a BFS search?
The usual (recommended) technique is to write a visitor that throws an exception (preferably a custom one that you define) when your goal vertex is reached. Your code that calls BFS or Dijkstra can just wrap a try block that catches your exception. -- Jeremiah Willcock