Make Boost Dijkstra algorithm stop when it reaches a destination node

Question

I'm using boost::graph and its Dijkstra implementation.

When someone is using the Dijkstra algorithm, it may be to know the shortest path between 2 nodes in a graph. But as you need to check all nodes in the graph to find the shortest path, usually (like the boost algorithm) Dijkstra gives you back all the distances between one origin point, and all the other nodes of the graph.

One easy improvement of this algorithm when you only want the path between 2 nodes is to stop it when the algorithm reach the destination node. Then, you are sure that the distance that you have for this final destination node is the shortest one.

How can one tell the boost Dijkstra algorithm to stop when it reaches a specific node ?

Answer 1

You can throw an exception from the visitor: FAQ

How do I perform an early exit from an algorithm such as BFS?

Create a visitor that throws an exception when you want to cut off the search, then put your call to breadth_first_search inside of an appropriate try/catch block. This strikes many programmers as a misuse of exceptions, however, much thought was put into the decision to have exceptions has the preferred way to exit early. See boost email discussions for more details.

Answer 2

Thanks to Sehe and his insights, I followed the road of the Dijkstra Visitors to solve my problem. Here is the solution :

I created a visitor class that came from the Dijkstra's visitor types :

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>

// Graph Definitions
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
typedef boost::graph_traits<Graph>::edge_descriptor Edge;

// Visitor that throw an exception when finishing the destination vertex
class my_visitor : boost::default_bfs_visitor{
protected:
  Vertex destination_vertex_m;
public:
  my_visitor(Vertex destination_vertex_l)
    : destination_vertex_m(destination_vertex_l) {};

  void initialize_vertex(const Vertex &s, const Graph &g) const {}
  void discover_vertex(const Vertex &s, const Graph &g) const {}
  void examine_vertex(const Vertex &s, const Graph &g) const {}
  void examine_edge(const Edge &e, const Graph &g) const {}
  void edge_relaxed(const Edge &e, const Graph &g) const {}
  void edge_not_relaxed(const Edge &e, const Graph &g) const {}
  void finish_vertex(const Vertex &s, const Graph &g) const {
    if (destination_vertex_m == s)
      throw(2);
  }
};

And then I launched Boost Dijkstra with a try-catch block to get the exception

// To store predecessor
std::vector<Vertex> predecessor_map_p (boost::num_vertices(graph_m)); 
// To store distances
std::vector<double> distance_map_p (boost::num_vertices(graph_m)); 
// Vertex that will have set to the origin and the destination :
Vertex vertex_origin_num_p,vertex_destination_num_p;

// Visitor to throw an exception when the end is reached
my_visitor vis(vertex_destination_num_p);

try {
  boost::dijkstra_shortest_paths(
    graph_m, 
    vertex_origin_num_p,
    predecessor_map(boost::make_iterator_property_map(predecessor_map_p->data(), vid_l)).
    distance_map(boost::make_iterator_property_map(distance_map_p->data(), vid_l)).
    visitor(vis)
  );
}
catch (int exception) {
  std::cout << "The Dijsktra algorithm stopped" << std::endl;
}