让Boost Dijkstra算法在到达目的节点时停止

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

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

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

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

您可以从访问者处抛出异常：FAQ http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/faq.html

如何提前退出 BFS 等算法？

创建一个访问者，当您想要中断搜索时抛出异常，然后将对 breadth_first_search 的调用放在适当的 try/catch 块内。这让许多程序员认为这是对异常的滥用，但是，经过深思熟虑，才决定让异常具有提前退出的首选方式。有关更多详细信息，请参阅增强电子邮件讨论。