ベルマンフォードとダイクストラのアルゴリズムの違い

Question

2   1 
1----------2---------4 
|   |   | 
|3   |3  |1 
| 6  |   | 
3---------5 --------- 

これはグラフです。ソースノードは1、宛先ノードは5

です。

両方のアルゴリズムが同じ出力を出すかどうか つまり、両方とも1->2->4->5を返しますか？ （ダイクストラの負の重みは許されないことを除いて）

ご協力いただきありがとうございます。

Answer 1

Bellman-Fordアルゴリズムは、負のエッジ重みを可能にし、グラフ内の負のサイクルを検出できる単一ソースの最短パスアルゴリズムです。

Dijkstraアルゴリズムもまた、単一ソースの最短経路アルゴリズムです。ただし、すべてのエッジの重みは負でなければなりません。

あなたのケースでは、グラフのエッジが負の重みを持たないため、合計コストに関する限り、違いはありません。しかし、Bellman-FordアルゴリズムはO(|V||E|)の複雑さを有するが、バイナリヒープによる典型的な実装はTheta((|E|+|V|)log|V|)時間の複雑さを有するので、Dijkstraのアルゴリズムが通常使用される。

最小コストを持つパスが2つ以上ある場合、実際に返されるパスは実装に依存します（同じアルゴリズムであっても）。

Answer 2

ダイクストラのアルゴリズムの頂点には、ネットワークの全情報が含まれています。すべての頂点がそれ自身とその隣人を気にするようなものはありません。一方、Bellman-Fordアルゴリズムのノードには、関連する情報のみが含まれています。この情報により、そのノードは、それが接続できる隣接ノードと、その関係が相互に由来するノードを知ることができます。 DijkstraのアルゴリズムはBellman-Fordのアルゴリズムより高速ですが、2番目のアルゴリズムはパスの負の重みなどのいくつかの問題を解決するのに役立ちます。