どちらも、単一のソースからの最短経路を見つけるために使用できます。BFS は で実行されますO(E+V)が、ダイクストラ法は で実行されますO((V+E)*log(V))。
また、ダイクストラ法はルーティング プロトコルでよく使用されているのを見ました。
したがって、BFS が同じことをより速く実行できる場合、なぜ Dijkstra のアルゴリズムを使用するのでしょうか?
ベストアンサー1
Dijkstra では、各ステップに 1 以外の距離を割り当てることができます。たとえば、ルーティングでは、距離 (または重み) を速度、コスト、優先度などによって割り当てることができます。その後、アルゴリズムは、ソースからトラバースされたグラフ内のすべてのノードまでの最短パスを提供します。
一方、BFSは基本的に、反復ごとに検索を1つの「ステップ」（リンク、エッジ、アプリケーションで呼びたい名前）だけ拡大するだけであり、最小のものを見つける効果があります。歩数ソース（「ルート」）から任意のノードに到達するのにかかる時間。