[解決済み] Breadth-First SearchはShortest Pathを探すときにどのように機能しますか？

質問

いくつか調べてみたのですが、このアルゴリズムの小さな部分が欠けているようです。Breadth-First Searchがどのように機能するかは理解していますが、個々のノードがどこに行けるかを教えてくれるのとは対照的に、具体的にどのように特定の経路に導いてくれるのかがわかりません。私の混乱を説明する最も簡単な方法は、例を挙げることだと思います。

例えば、こんなグラフがあったとします。

そして、私の目標はAからEに行くことです（すべてのエッジは非重み付け）。

Aは私の原点なので、Aから始めます。Aをキューに入れ、すぐにキューを解除して探索します。AはBとDにつながっているので、BとDの両方を待ち行列に入れます。

Bをキューから外し、探索すると、A（すでに探索済み）とCにつながることがわかったので、Cをキューに入れました。そして C を待ち行列から外すと、それもまた私のゴールである E につながっていることがわかります。

最短経路がA->D->Eであることは論理的に分かっているのですが、幅優先探索が具体的にどう役立つのか分かりません。

また、実際には木を使っていないので、quot;parent"ノードはなく、子だけであることに注意してください。

どのように解決するのですか？

技術的には、Breadth-first search (BFS) 自体は、最短経路を見つけることはできません。BFSはグラフを探索するための戦略を記述していますが、特に何かを探索しなければならないとは言っていません。

ダイクストラのアルゴリズム は、BFSを応用して、単一ソースの最短経路を求めることができるようにしたものです。

原点からあるノードまでの最短経路を求めるには、グラフ内の各ノードについて、現在の最短距離と、最短経路の直前のノードの2項目を保持する必要がある。初期状態では、すべての距離は無限大に設定され、すべての先行ノードが空に設定されている。この例では、Aの距離を0に設定し、BFSを実行する。各ステップにおいて、子孫の距離を改善できるかどうか、つまり、原点から先行ノードまでの距離と探索中のエッジの長さが、当該ノードの現在の最適距離より小さいかどうかをチェックします。距離を改善できる場合は、新しい最短経路を設定し、その経路を獲得した前任者を記憶しておく。BFSキューが空になったら、あるノード（この例ではE）を選び、その先行者を辿って原点に戻る。そうすると、最短経路が得られる。

少しわかりにくいかもしれませんが、wikipediaにあるように 疑似コードセクション を紹介します。