1. ホーム
  2. algorithm

[解決済み] Breadth First Search (BFS)が同じことをより速くできるのに、なぜDijkstraのアルゴリズムを使うのですか?

2022-05-15 11:49:19

疑問点

BFSとBFSは、どちらも単一ソースからの最短経路を求めるために用いることができる。BFSは O(E+V) で実行され、Dijkstra の場合は O((V+E)*log(V)) .

あと、ルーティングプロトコルのようにDijkstraがよく使われているのを見かけますね。

では、なぜBFSの方が速いのに、Dijkstraのアルゴリズムを使っているのでしょうか?

どのように解決するのか?

ダイクストラでは、各ステップに対して1以外の距離を割り当てることができます。たとえば、ルーティングでは、距離 (または重み) は速度、コスト、優先度などによって割り当てることができます。そして、アルゴリズムは、ソースからトラバースされたグラフのすべてのノードへの最短経路を与えます。

一方、BFS は基本的に、反復ごとに 1 つの「ステップ」(リンク、エッジなど、アプリケーションで呼びたいもの)だけ探索を拡張し、その結果、最小の ステップの数 これは、ソース (「ルート」) から任意のノードに到達するために必要な最小の ステップ数 を見つける効果があります。