algorithm - 重み付けされていないグラフを介したノードの最短シーケンス

Question

ヘッドノードからテールノードまでのグラフからノードの最短シーケンスを見つけるアルゴリズムがあるかどうか知りたいです。グラフはヘッドノードから分岐し、任意に複雑で、テールノードに収束します。ノード間のすべての接続は重み付けされていません。

頭と尾のノードから、グラフの両端のノードが接触するまで、この問題に取り組むことを検討していますが、「より良いホイール」が存在するかどうかを（再）発明する前に知りたいです。 。

Answer 1

O（E + V）で実行される幅優先探索を使用します。これは、重み付けされていないグラフで得られる最速です。

Answer 2

これは、コンピュータサイエンスの美しい「標準的な」問題の1つです。グラフの説明を前提として、最初にダイクストラのアルゴリズムを確認する必要があります

Answer 3

BFSは、これらのタイプの問題に最適です。単一ノードの最短パスを見つけたい場合でも、グラフ全体をトラバースして、すでに取得されている最短パス以外の可能なパスがあるかどうかを調べます。

ソースノードと任意の（単一の）ノード間の最短ルートを正確に示すBFSツリーを描画することもできます。