1. 序章

このチュートリアルでは、DijkstraとFloyd-Warshallの最短経路アルゴリズムの主な違いについて説明します。 さらに、理解を深めるために、さまざまなプロパティに基づいてそれらを比較します。

どちらのアルゴリズムも、グラフと呼ばれるデータ構造のクラスに適用されます。 グラフは、とラベル付けされたノードまたは頂点のセットと、とラベル付けされたこれらのノード間の接続またはエッジのセットによって特徴付けられます。 さらに、ノードのペア間の距離メトリックを表す非負の整数の重みを各エッジに割り当てます。 2つのノード間のパスには、その構成エッジの重みの合計である距離があります。 これを念頭に置いて、 t 重要なアイデアは、ノードのペア間の距離が最小のパスを見つけることです。

上記の例では、および。 重みはエッジの上に表示されます。

これに対応して、これらのアルゴリズムが解決する特定の問題を思い出します。

2. ダイクストラのアルゴリズム

単一ソース最短経路（SSSP）問題を解決します。 つまり、単一の送信元ノードから特定の宛先ノードへの最短パスを見つけたいと考えています。 このアルゴリズムの適切なアプリケーションは、リンクステートルーティングプロトコルにあり、各ノードはそれを使用してネットワークの内部画像を作成します。

3. フロイド-ウォーシャルアルゴリズム

All-Pairs Shortest Paths（APSP）問題を解決します。 特に、グラフ内のノードの all ペア間の最短経路が見つかります。これは、計算コストが高くなります。 この計算コストは、グラフデータの保存に必要なスペースとそれを処理するために必要な時間の両方に現れます。 それにもかかわらず、Floyd-Warshallアルゴリズムは、実装が単純であるため、引き続き有用です。

4. 比較

このセクションでは、各アルゴリズムのプロパティに基づいて並べて比較します。

4.1. アルゴリズムのパラダイム

ダイクストラのアルゴリズムは、貪欲なパラダイムに従います。 つまり、各ステップでローカルに最適な選択を行い、終了時にグローバルに最適なソリューションを導き出します。 欲張りアルゴリズムが解決できる問題の特徴は、最適部分構造と欲張り選択特性です。 このようなアルゴリズムはトップダウン方式で実行されます。

最適な部分構造とは、問題の最適な解決策がそのサブ問題の最適な解決策で構成されていることを意味します。 たとえば、SSSP問題は最適な部分構造を持っていますが、 Unweighted Longest SimplePath問題は持っていません。

貪欲な選択プロパティは、アルゴリズムが最初のステップで貪欲な選択を行う場合、それと互換性のある最適なソリューションが存在することを示しています。 特に、貪欲な選択をすることは、私たちが解決しなければならないサブ問題を制限します。

対照的に、Floyd-Warshallのアルゴリズムは、動的計画法（DP）パラダイムに従います。 このようなアルゴリズムは、メモ化を適用してトップダウンで実行するか、ソリューションをボトムアップで構築します。 DPによって解決可能な問題は、最適な部分構造と重複する部分問題を持っています。

同じサブ問題がアルゴリズムの複数のステップで解決される場合、問題には重複するサブ問題があると言われます。 したがって、そのサブ問題スペースは十分に小さいため、新しいサブ問題は生成されません。

4.2. 漸近解析

全体として、ダイクストラのアルゴリズムを実装する方法は3つあります。

  • arrays ：キー操作のコストを挿入および削減し、最小抽出コストを削減して、全体に導きます。
  • min-heaps ：キーと最小抽出の操作コストを削減し、それぞれ実行と時間を削減します。 これは全体的に与えます。
  • フィボナッチヒープ：主要なコストと最小抽出コストを削減します。 これは全体的に与えます。

さらに、隣接リストベースの実装を想定すると、そのスペースの複雑さはです。

対照的に、Floyd-Warshallは、2D配列として実装されている隣接行列で動作します。 その時間と空間の複雑さはそれぞれとです。

4.3. 制限事項

ダイクストラのアルゴリズムは、負の重みエッジを持つグラフに正解を出力できない場合があります。

ただし、Floyd-Warshallは、負の重みエッジが存在する場合でも正確性を保証します。 また、グラフ内の負の重みのサイクルを検出することもできます。

5. 結論

要約すると、この記事では2つの重要な最短経路アルゴリズムについて説明しました。 また、主要なパラメーターについても対比しました。