複数の入り口と複数の出口に適したBFSのような最適なパスアルゴリズムは何ですか？

Question

私は、開始ノードから最も近い出口ノードまでの最適なパスを見つける最適なパスアルゴリズムを探しています。

この場合のグラフは正方形のグリッドであり、ネイバースクエアへのすべてのコストは1です。 これらの制限を使用する最適化は問題ありません。

ランダムに選択した入り口から四角形のグリッドを入力すると、指定した任意の出口に最も近いパスを検索することができます。

今まで私はBFSを何度もやっていましたが、すべての終了時に1回、結果を組み合わせました。私はこれが最も効果的な方法だとは思っていませんが。

Answer 1

すべての出口からBFSを開始します。新しい正方形を発見すると、最も近い出口までの距離は前の正方形の距離+1であり、パスの方向は前の正方形に向かっています。

（距離、方向）タプルは入力場所によって異なりますので、すべての四角形についてこれらの値を事前に計算しておくことができます。新しい入口から再開する必要はありません。