[解決済み] 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 つの「ステップ」(リンク、エッジなど、アプリケーションで呼びたいもの)だけ探索を拡張し、その結果、最小の ステップの数 これは、ソース (「ルート」) から任意のノードに到達するために必要な最小の ステップ数 を見つける効果があります。
関連
-
[解決済み】Dijkstraのアルゴリズムが負の重みのエッジに対して機能しないのはなぜですか?
-
[解決済み] 簡単な面接問題が難しくなった:1~100の数字が与えられたとき、ちょうどk個の数字が欠けていることを見つけなさい。
-
[解決済み] 短縮URLの作成方法を教えてください。[クローズド]
-
[解決済み] GenerativeアルゴリズムとDiscriminativeアルゴリズムの違いは何ですか?[クローズド]
-
[解決済み】画像処理。コカ・コーラ缶」認識のためのアルゴリズム改良
-
[解決済み] 3つ以上の数値の最小公倍数
-
[解決済み] ハッシュテーブルとトライ(プレフィックスツリー)のどちらを選べばいいですか?
-
[解決済み] O(1), O(n log n), O(log n)の複雑さを持つアルゴリズムの例
-
[解決済み] 配列から、和が指定された数に等しい要素の組を求めよ。
-
[解決済み] ロードされたサイコロをシミュレートするための効率的なデータ構造とアルゴリズムとは?
最新
-
nginxです。[emerg] 0.0.0.0:80 への bind() に失敗しました (98: アドレスは既に使用中です)
-
htmlページでギリシャ文字を使うには
-
ピュアhtml+cssでの要素読み込み効果
-
純粋なhtml + cssで五輪を実現するサンプルコード
-
ナビゲーションバー・ドロップダウンメニューのHTML+CSSサンプルコード
-
タイピング効果を実現するピュアhtml+css
-
htmlの選択ボックスのプレースホルダー作成に関する質問
-
html css3 伸縮しない 画像表示効果
-
トップナビゲーションバーメニュー作成用HTML+CSS
-
html+css 実装 サイバーパンク風ボタン