いくつかの最短経路アルゴリズムの比較

最短経路問題は、グラフ理論研究における古典的なアルゴリズム問題であり、グラフ（ノードとパスで構成される）内の 2 つのノード間の最短経路を見つけることを目的としています。

アルゴリズムの具体的な形式は次のとおりです。

出発点を決定する最短経路問題: つまり、出発ノードがわかっている場合に最短経路を見つける問題。

終点がわかっている最短経路問題は、始点を決定する問題の逆です。この問題は、終点ノードがわかっている場合に最短経路を見つけることです。無向グラフでは、この問題は開始点を決定する問題とまったく同じです。有向グラフでは、この問題はすべてのパスの方向を逆にして開始点を決定する問題と同等です。

開始点と終了点を決定する最短経路問題。つまり、開始点と終了点が与えられた場合、2 つのノード間の最短経路を見つけます。

グローバル最短経路問題: グラフ内のすべての最短経路を見つけます。

フロイド

複数のソースがあり、負の重みエッジがない最短パスを見つけます。マトリックスを使用してグラフを記録します。適時性は低く、時間計算量は O(V^3) です。

フロイド・ワーシャルアルゴリズムは、任意の 2 点間の最短経路を解くアルゴリズムです。有向グラフや負の重み付き最短経路問題を正しく処理できます。

Floyd-Warshall アルゴリズムの時間計算量は O(N^3) で、空間計算量は O(N^2) です。

フロイド・ワーシャルの原理は動的計画法です。

Di,j,k を、中間ノードとして (1..k) セット内のノードのみを持つ i から j への最短パスの長さとします。

最短経路が点 k を通過する場合、Di,j,k = Di,k,k-1 + Dk,j,k-1 となります。

最短経路が点 k を通過しない場合は、Di,j,k = Di,j,k-1 となります。

したがって、Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1) となります。

実際のアルゴリズムでは、スペースを節約するために、元のスペースに対して直接反復処理を実行し、スペースを 2 次元に縮小することができます。

Floyd-Warshall アルゴリズムの説明は次のとおりです。

 k ← 1 から nまで 
 i ← 1 から nまで 
 j ← 1 から nまで 
 (Di,k + Dk,j < Di,j)の場合
Di,j ← Di,k + Dk,j;

ここで、Di,j はポイント i からポイント j までのコストを表します。Di,j が ∞ の場合、2 つのポイント間に接続がないことを意味します。

ダイクストラ

単一のソースと負の重みのない最短パスを見つけます。適時性は良好で、時間計算量は O (V*V+E) です。

ソースポイントが到達可能な場合、O(V*lgV+E*lgV)=>O(E*lgV)。

疎グラフの場合、E = V * V / lgVなので、アルゴリズムの時間計算量はO（V ^ 2）になります。フィボナッチヒープを優先キューとして使用する場合、アルゴリズムの時間計算量は O (V*lgV + E) になります。

ベルマンフォード

単一のソースから最短経路を見つける場合、負の重み付きループがあるかどうかを判断できます (ある場合、最短経路はありません)。この方法は時間効率が良く、時間計算量は O(VE) です。

ベルマン・フォードアルゴリズムは、単一ソースの最短経路問題を解決するためのアルゴリズムです。

単一のソースポイントに対する最短経路問題とは、重み付き有向グラフ G とソースポイント s が与えられた場合に、グラフ G 内の任意のポイント v について、s から v への最短経路を見つけることを意味します。

Dijkstra アルゴリズムとは異なり、Bellman-Ford アルゴリズムでは、エッジの重みは負になることがあります。グラフ内にサイクル（v から始まり、いくつかの点を通過して v に戻る）が見つかり、このサイクル内のすべてのエッジの重みの合計が負であるとします。そして、このループを通じて、ループ内の任意の 2 点間の最短経路は無限に小さくなる可能性があります。この負のループが処理されない場合、プログラムは永久に実行されます。 Bellman-Ford アルゴリズムには、このような負のループを区別する機能があります。

SPFA

これは、比較的適時性と時間計算量が O(kE) に優れたベルマン・フォードキュー最適化です。 (k<<V)。

Bellman-Ford アルゴリズムと同様に、SPFA アルゴリズムは一連の緩和操作を使用して、グラフ内の特定のノードから他のすべてのノードへの最短パスを取得します。違いは、SPFA アルゴリズムがキューを維持するため、ノードの現在の最短パスが更新された後、他のノードをすぐに更新する必要がないため、繰り返し操作の数が大幅に削減されることです。

SPFA アルゴリズムは、ダイクストラアルゴリズムとは異なり、負のエッジ重みを持つグラフに使用できます。

Dijkstra アルゴリズムや Bellman-ford アルゴリズムとは異なり、SPFA の時間効率は不安定です。つまり、異なるグラフに必要な時間は大きく異なります。

最良のケースでは、各ノードは一度だけキューに入れられ、アルゴリズムは実際には幅優先のトラバーサルになり、時間の複雑さは O(E) のみになります。一方、各ノードが (V-1) 回キューに入れられる例もあり、その場合、アルゴリズムは時間計算量が O(VE) のベルマンフォードアルゴリズムに退化します。

SPFA アルゴリズムは、負のエッジ重みグラフ上の Bellman-Ford アルゴリズムを完全に置き換えることができ、スパースグラフでも優れたパフォーマンスを発揮します。ただし、非負のエッジ重みグラフでは、最悪の事態を回避するために、より効率的で安定した Dijkstra アルゴリズムとそのヒープ最適化バージョンが通常使用されます。従来の SPFA アルゴリズムは、グリッドグラフのクラスではパフォーマンスが低下します。

【編集者のおすすめ】