Re: [Boost-users] Termination of breadth first search

Subject: Re: [Boost-users] Termination of breadth first search
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-05-12 17:11:46

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