143

両方を使用して、単一のソースから最短パスを見つけることができます。BFS は で実行されますO(E+V)が、ダイクストラは で実行されO((V+E)*log(V))ます。

また、ダイクストラがルーティング プロトコルとよく似た方法で使用されているのを見てきました。

では、BFS が同じことをより高速に実行できるのに、なぜダイクストラのアルゴリズムを使用するのでしょうか?

4

6 に答える 6

190

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

一方、BFS は基本的に、反復ごとに 1 つの「ステップ」(リンク、エッジ、アプリケーションで呼びたいもの) だけ検索を拡張するだけです。ソース (「ルート」) からの特定のノード。

于 2010-09-29T00:58:54.553 に答える
30

旅行 Web サイトを検討する場合、これらはノードの重み (距離) のためにダイクストラのアルゴリズムを使用します。

すべてのノード間の距離が同じであると考える場合は、BFS を選択することをお勧めします。

たとえば、A -> (B, C) -> (F)エッジの重みがA->B= 10、A->C= 20、B->F= C->F= 5 であるとします。

ここで、BFS を適用すると、どちらも (エッジの数に関して) 最短経路であるため、答えは ABF または ACF になりますが、Dijstra を適用すると、答えは ABF のみになります。道。

于 2013-08-10T11:19:14.683 に答える
0
  • BFS は、最短パスをステップ エッジの数としてカウントする場合、またはアプリケーションがすべてのエッジに同一の (ただし正の) 重みを割り当てる場合にのみ機能します。
  • BFS と Dijkstra の違いは、FIFO キューをプライオリティ キューに置き換えただけです。

これは、エッジの正の重み制約を修正しないことに注意してください。有名なダイクストラ (および BFS) の欠点は、スピード ペナルティを支払うことで Bellman-Ford によって修正されています。

出典: Erickson, Jeff (2019) の第 8.4 章、第 8.6 章。アルゴリズム

于 2021-11-26T02:37:00.493 に答える