少し調べてみたのですが、このアルゴリズムの小さな部分が 1 つ抜けているようです。幅優先探索の仕組みは理解していますが、個々のノードがどこに行くことができるかを示すだけでなく、特定のパスにどうやって到達するのかが正確にはわかりません。私の混乱を説明するには、例を挙げるのが一番簡単だと思います。
たとえば、次のようなグラフがあるとします。
そして私の目標は、A から E に到達することです (すべてのエッジは重み付けされていません)。
A から始めます。これが私の原点だからです。A をキューに入れ、その後すぐに A をキューから外して探索します。A は B と D に接続されているため、B と D が生成されます。したがって、B と D の両方をキューに入れます。
B をキューから外して探索すると、A (すでに探索済み) と C につながることがわかったので、C をキューに入れます。次に D をキューから外すと、目標の E につながることがわかったので、C をキューに入れます。次に C をキューから外すと、これも目標の E につながることがわかったので、C をキューに入れます。
最速のパスは A->D->E であることは論理的にわかっていますが、幅優先探索がどのように役立つのかよくわかりません。終了時に結果を分析して最短パスが A->D->E であることが確認できるように、パスを記録するにはどうすればよいのでしょうか。
また、実際にはツリーを使用していないため、「親」ノードはなく、子のみがあることに注意してください。
ベストアンサー1
技術的には、幅優先探索 (BFS) だけでは最短経路を見つけることはできません。これは、BFS が最短経路を探すわけではないためです。BFS はグラフを検索するための戦略を説明しますが、特に何かを検索する必要があるとは述べていません。
ダイクストラのアルゴリズムBFS を適応させて、単一ソースの最短パスを見つけられるようにします。
起点からノードまでの最短経路を取得するには、グラフ内の各ノードについて、現在の最短距離と、最短経路内の前のノードという 2 つの項目を維持する必要があります。最初は、すべての距離が無限大に設定され、すべての先行ノードは空に設定されています。例では、A の距離を 0 に設定してから、BFS に進みます。各ステップで、子孫の距離を改善できるかどうかを確認します。つまり、起点から先行ノードまでの距離と、探索しているエッジの長さを加えた値が、問題のノードの現在の最適距離よりも短いかどうかを確認します。距離を改善できる場合は、新しい最短経路を設定し、その経路が取得された先行ノードを記憶します。BFS キューが空になったら、ノード (例では E) を選択し、その先行ノードを起点までトラバースします。これにより、最短経路が得られます。
もしこれが少しわかりにくいように思えるなら、Wikipediaに良い説明があります擬似コードセクション話題になっている。