使Boost Dijkstra算法到达目标节点时停止 [英] Make Boost Dijkstra algorithm stop when it reaches a destination node

问题描述

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

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

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

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

解决方案

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

我该如何

创建一个访问者，当您想切断搜索时会引发异常，然后将调用权放在适当的try /内，使其进入广度头（first）捕获块。这使许多程序员误认为是对异常的滥用，但是，很多人考虑让异常具有优先退出的决定。有关更多详细信息，请参见增强电子邮件的讨论。

I'm using boost::graph and its Dijkstra implementation.

When someone is using the Dijkstra algorithm, it may be to know the shortest path between 2 nodes in a graph. But as you need to check all nodes in the graph to find the shortest path, usually (like the boost algorithm) Dijkstra gives you back all the distances between one origin point, and all the other nodes of the graph.

One easy improvement of this algorithm when you only want the path between 2 nodes is to stop it when the algorithm reach the destination node. Then, you are sure that the distance that you have for this final destination node is the shortest one.

How can one tell the boost Dijkstra algorithm to stop when it reaches a specific node ?

解决方案

You can throw an exception from the visitor: 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.

这篇关于使Boost Dijkstra算法到达目标节点时停止的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！