多くのグーグル検索の後、ほとんどの情報源が、ダイクストラ アルゴリズムはベルマン フォード アルゴリズムよりも「効率的」であると言っていることがわかりました。しかし、Bellman-Ford アルゴリズムが Dijkstra アルゴリズムよりも優れているのはどのような状況でしょうか?
「より良い」というのは大雑把な言い方であることは承知しています。具体的には、速度と、それが当てはまる場合はスペースのことを意味します。確かに、Bellman-Ford アプローチが Dijkstra アプローチよりも優れている状況がいくつかあります。
Bellman-Ford アルゴリズムは単一ソースの最短経路アルゴリズムであるため、エッジの重みが負の場合、グラフ内の負のサイクルを検出できます。
2 つの唯一の違いは、Bellman-Ford は負の重みも処理できるのに対し、ダイクストラ アルゴリズムは正の重みしか処理できないことです。
ウィキから
ただし、ダイクストラのアルゴリズムは、まだ処理されていない最小の重みのノードを貪欲に選択し、すべての出力エッジでこの緩和プロセスを実行します。対照的に、Bellman–Ford アルゴリズムは単純にすべてのエッジを緩和し、これを |V | 行います。− 1 回、ここで |V | グラフの頂点の数です。これらの繰り返しのそれぞれで、正しく計算された距離を持つ頂点の数が増え、最終的にすべての頂点が正しい距離を持つことになります。この方法により、Bellman–Ford アルゴリズムを Dijkstra よりも広いクラスの入力に適用できます。
ただし、典型的なバイナリ ヒープ優先度キューの実装には O((|E|+|V|)log|V|) 時間の複雑さがある [フィボナッチ ヒープ優先度キューは O( |V|log|V| + |E|)]、Bellman-Ford アルゴリズムの複雑さは O(|V||E|) です。
私が知っているそれらの間には4つの大きな違いがあります:- 1.ベルマン時間の複雑さはO(VE)で、ダイクストラアルゴリズムはmaxheapが使用されている場合はO(ElogV)です。
完全には同意しません。違いは実装と複雑さにあります。Dijsktra のアルゴリズムは高速 (O(n^2)) ですが実装が難しく、Bellman Ford の複雑さは O(n^3) ですが実装が簡単です。