"Floyd-Warshall アルゴリズム"と"Dijkstra's Algorithm"の違いは何ですか? また、グラフ内の最短経路を見つけるのに最適なのはどれですか?
次のように、ネット内のすべてのペア間の最短経路を計算し、結果を配列に保存する必要があります。
**A B C D E**
A 0 10 15 5 20
B 10 0 5 5 10
C 15 5 0 10 15
D 5 5 10 0 15
E 20 10 15 15 0
Dijkstraのアルゴリズムは、ノードとグラフ内の他のすべてのノードとの間の最短経路を見つけます。ノードごとに 1 回実行します。重みは負でない必要があるため、必要に応じて、最初にグラフの値を正規化する必要があります。
Floyd-Warshallは、1 回の実行ですべてのノード ペア間の最短ルートを計算します。サイクルの重みは非負である必要があり、グラフは方向付けられている必要があります (ダイアグラムはそうではありません)。
Johnsonのアルゴリズムは、Dijkstra のアルゴリズムを使用して 1 回のパスですべてのペアを見つけており、まばらなツリーの方が高速です (分析のリンクを参照してください)。
Floyd Warshall は頂点のすべてのペア間のパスを見つけますが、Dijkstra は 1 つの頂点から他のすべての頂点へのパスのみを見つけます。
Floyd Warshall は O(|V| 3 ) で、Dikstra は O(|E| + |V| log |V|) ですが、O(|E の複雑さを与えるすべてのペアを見つけるには V 回実行する必要があります。 * V| + |V 2 | log |V|) そうですね。これは、FW アルゴリズムよりも Dijsktra を繰り返し使用する方がおそらく高速であることを意味します。両方のアプローチを試して、実際のケースでどちらが最速かを確認します。
Dijkstra は1 つの頂点のみから最短経路を見つけますが、Floyd-Warshall はそれらすべての間で最短経路を見つけます。
ダイクストラのアルゴリズムよりも実行時間が (はるかに) 長いため、頂点のすべてのペア間の最短経路を見つけたい場合は、Floyd-Warshall アルゴリズムを使用します。
Floyd-Warshall アルゴリズムの最悪の場合のパフォーマンスは O(|V| 3 ) ですが、ダイクストラの場合の最悪の場合のパフォーマンスは O(|E| + |V|log |V|) です。
一方、単一ソースの最短経路問題に対するより優れたアルゴリズムが知られています。実際に関連するものは、Torben Hagerup による Dijkstra のアルゴリズムの派生です。アルゴリズムの最悪の場合の複雑さは Djikstra のものと同じですが、平均的なケースでは、期待される実行時間はグラフのサイズに比例し、純粋な Dijkstra よりもはるかに高速です。アルゴリズムの考え方は、常にキューから最小エッジをポーリングする必要がないという考え方に基づいています。キューからエッジをポーリングすることができます。このエッジの1+k重みは、エッジの最小重みの倍にkなり0ます。そのようなエッジが選択された場合でも、アルゴリズムは最短パスを見つけます。
Dijkstra は主に、1 つのノードから他のすべてのノードへの単一ペアの最短パスの検索に使用されます。一方、Floyd-Warshall は、すべてのペアの最短パス、つまり頂点のすべてのペア間の最短パスに使用されます。Floyd-Warshall アルゴリズムの最悪の場合のパフォーマンスは O(|V|3) ですが、Dijkstra の場合の最悪の場合のパフォーマンスは O(|E| + |V|log |V|) になります。また、Dijkstra のアルゴリズムは負の重みには使用できません。 （ベルマンフォードを使用しています）。しかし、Floyd-Warshall では、負の重みを使用できますが、負のサイクルは使用できません