[解決済み] ベルマンフォードとダイクストラの比較。どのような状況下でベルマンフォードが優れているか？

質問

いろいろとググってみたところ、ほとんどの情報源で、ダイクストラ・アルゴリズムはベルマン-フォード・アルゴリズムよりも"効率的"であると書かれていることがわかりました。しかし、どのような状況であれば、ベルマンフォードアルゴリズムはダイクストラアルゴリズムよりも優れているのでしょうか？

具体的には、スピードと、スペースという意味です。ベルマンフォードアプローチがダイクストラアプローチより優れている状況があることは確かです。

どのように解決するのですか？

ベルマンフォードアルゴリズムはシングルソースの最短経路アルゴリズムなので、負のエッジの重みがある場合、グラフ内の負のサイクルを検出することができます。

両者の唯一の違いは、ベルマンフォードは負の重みも扱えるのに対して、ダイクストラアルゴリズムは正の重みしか扱えないことである。

より ウィキ

しかし、Dijkstraのアルゴリズムでは、貪欲に最小重量のノード この緩和処理は、まだ処理されていないものに対して行われます。 これに対して、ベルマンフォードアルゴリズムは、そのすべての出射エッジに対して 単純にすべてのエッジを緩和し、これを｜V｜-1回行う、ここで｜V｜は はグラフの頂点の数である。この繰り返しのそれぞれで 正しく計算された距離を持つ頂点の数が増え、そこから であり、最終的にはすべての頂点が正しい値を持つことになる。 の距離です。 この方法によって、ベルマンフォードアルゴリズムを適用することができます。 は、Dijkstraよりも広い範囲の入力に対応することができます。

しかし、Dijkstraは一般的に負の重みのエッジがない場合に優れていると考えられており、典型的なバイナリヒープ優先順位キューの実装はO((|E|+|V|)log|V|)の時間複雑性を持ち［フィボナッチヒープ優先順位キューはO(|V|log|V| + |E|)を与える］、ベルマン-フォードアルゴリズムは O(|V||E|) 複雑性を持っているからである。