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

Question

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

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

当您只想要2个节点之间的路径时，这个算法的一种简单改进是在算法到达目标节点时停止。然后，您可以确定对于此最终目标节点，您拥有的距离是最短的。

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

- Emmanuel Jay

Answer 1

你可以在访问者中抛出异常：FAQ 创建一个 visitor，当您想要终止搜索时，抛出异常，然后将 breadth_first_search 的调用放置在适当的 try/catch 块中。这被许多程序员视为异常用法，但是，在决定使用异常作为早期退出的首选方式时，考虑了很多思想。有关更多详细信息，请参见 boost 邮件讨论。

- sehe

---

你能在C++中使用try-catch块吗？我认为访问者模式是正确的方法，但像往常一样，实现boost概念有点困难。（顺便问一下，你是神Sehe吗？你编写了Boost吗？）编辑：我是个白痴，这是C++的基本结构...^^"抱歉。 - Emmanuel Jay

实现BGL访问者非常容易。文档中包含了示例（例如程序）的样本。 - sehe

Answer 2

感谢Sehe及其见解，我遵循Dijkstra访问者的方法解决了我的问题。以下是解决方案：

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

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

- Emmanuel Jay

---

哇，我有点不爽你选择取消接受那个答案。你本可以把这个作为对答案的评论发表。我的意思是，你甚至没有在问题中发布一行代码（否则我会为你展示代码！） - sehe

@sehe没错。我认为提供一个让事情正常运转的示例很有用……这是我的失误，Boost Graph之神；）我还有一个问题要问你：如果您想让访问者修改某些内容怎么办？它似乎是一个const函数… - Emmanuel Jay

哦，是的，一个例子很有用。我会为此点赞 :) （仅仅因为它使用了问题中没有提供的信息，所以才更好，这有点奇怪）。谢谢。 - sehe

在修改方面，通常的方法是保留要修改的变量的引用。PropertyMaps 已经完全采用了这种方法，以至于所有属性映射都是逻辑上的引用-根据定义。一个可能的替代语法是传递 boost::ref(my_visitor)（但我不确定它是否有效，在这种情况下没有使用过）。无论如何，这种语法通常对函数对象有效，因为 reference_wrapper 转发函数调用运算符。 - sehe

@sehe 好的，我会诚实地说，这似乎超出了我对boost概念的理解范围...而且由于我的实习今天结束了，我不会再向您请教更多;)。非常感谢您所做的一切！我从您那里学到了很多！ - Emmanuel Jay

感谢你，非常感激。我希望你学得愉快，也相信你做得很好！ - sehe