使Boost Dijkstra算法在到达目标节点时停止

Question

我正在使用boost :: graph及其Dijkstra实现.

当有人使用Dijkstra算法时,可能知道图中2个节点之间的最短路径.但是,当您需要检查图中的所有节点以找到最短路径时,通常(如增强算法)Dijkstra会返回一个原点与图形的所有其他节点之间的所有距离.

当您只想要2个节点之间的路径时,该算法的一个简单改进是在算法到达目标节点时停止它.然后,您确定您对此最终目标节点的距离是最短的.

如何告诉boost Dijkstra算法在到达特定节点时停止？

Answer 1

您可以向访问者抛出异常:常见问题解答

如何从BFS等算法中提前退出？

如果要切断搜索,请创建一个抛出异常的访问者,然后在适当的try/catch块中调用breadth_first_search.这使得许多程序员滥用异常,然而,很多人认为将异常作为提前退出的首选方法的决定.有关详细信息,请参阅提升电子邮

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;
}