什么是适用于多入口和多出口的类似 BFS 的最优路径算法？

Question

我正在寻找一种最佳路径算法，该算法可以找到从任何起始节点到最近的出口节点的最佳路径。

本例中的图形是一个正方形网格，所有相邻正方形的成本都是 1。 使用这些限制的任何优化都很好。

基本上你是从一个随机选择的入口进入方格的，现在你想找到离任何给定出口最近的路径。

到现在为止，我多次执行 BFS，每次退出一次并合并结果。虽然我怀疑这是最有效的方法。

Answer 1

您从所有出口开始进行 BFS。当你发现一个新方块时，它到最近出口的距离是前一个方块的距离+1，路径方向是前一个方块。

由于 (distance,direction) 元组的 none 取决于您输入的位置，您可以为所有方块预先计算一次这些值，因此如果您重新开始，则不必重做搜索一个新的入口。