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

Question

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

有人在使用Dijkstra算法的时候，可能是想知道图中2个节点之间的最短路径。但是由于您需要检查图中的所有节点以找到最短路径，通常（如 boost 算法）Dijkstra 会返回一个原点与图中所有其他节点之间的所有距离。

当您只需要 2 个节点之间的路径时，此算法的一个简单改进是在算法到达目标节点时停止它。然后，你确定你到这个最终目的地节点的距离是最短的。

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

Answer 1

您可以从访问者那里抛出异常：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

感谢和他的见解，我按照 Dijkstra Visitors 的方法解决了我的问题。这是解决方案：

我创建了一个来自 Dijkstra 访问者类型的访问者 class：

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

然后我启动了带有 try-catch 块的 Boost Dijkstra 以获取异常

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

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

Make Boost Dijkstra algorithm stop when it reaches a destination node

c++11

dijkstra

boost-graph