什麼是適用於多入口和多出口的類似BFS的最優路徑算法？

Question

我正在尋找一種最佳路徑算法，可以找到從任何開始節點到最近的出口節點的最佳路徑。

這種情況下的圖形是一個正方形網格，鄰居方的所有成本都是1. 使用這些限制的任何優化都很好。

基本上，你從隨機選擇的入口進入方形網格，現在你想找到任何給定出口的最近路徑。

到目前爲止，我正在多次進行BFS，每次退出並結合結果。雖然我懷疑這是做這件事的最高性能方式。

Answer 1

你從所有出口開始做BFS。當你發現一個新的廣場時，距離最近的出口的距離是上一個廣場的距離+1，路徑方向是朝向前一個廣場。

由於沒有任何（距離，方向）元組取決於您輸入的位置，因此您可以預先計算所有方塊的這些值，因此如果您在新入口處重新開始，則不必重新搜索。