c++11 - 使 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.