フロイド・ウォーシャルアルゴリズム

コンピュータサイエンスにおいて、フロイド・ウォーシャルアルゴリズム（フロイドのアルゴリズム、ロイ・ウォーシャルアルゴリズム、ロイ・フロイドアルゴリズム、またはWFIアルゴリズムとも呼ばれる）は、正または負のエッジ重みを持つ有向重み付きグラフ（ただし負のサイクルは含まない）の最短経路を見つけるためのアルゴリズムである。 ^{[ 1 ] [ 2 ]}このアルゴリズムを1回実行すると、すべての頂点ペア間の最短経路の長さ（重みの合計）が見つかる。経路自体の詳細は返されないが、アルゴリズムを少し変更することで経路を再構築することは可能である。このアルゴリズムのバージョンは、関係の推移閉包を見つけるためにも、または（シュルツェ投票システムに関連して）重み付きグラフのすべての頂点ペア間の最も広い経路を見つけるためにも使用できる。

フロイド・ウォーシャルアルゴリズムは動的計画法の例であり、現在知られている形では1962 年にロバート・フロイドによって発表されました^{。[ 3 ]} しかし、これは基本的に、1959 年にバーナード・ロイによって発表されたアルゴリズム^{[4] や、1962 年にスティーブン・ウォーシャルによって発表されたグラフの推移閉包を見つけるアルゴリズム [5]}と本質^的に同じであり、^決定性^{有限オートマトンを}正規表現に変換するクリーネのアルゴリズム (1956 年に発表) と密接に関連しており、違いはmin - plus半環の使用です。^{[ 7 ]} 3 つの入れ子になった for ループとしてのアルゴリズムの現代的な定式化は、同じく 1962 年にピーター・インガーマンによって初めて記述されました。^{[ 8 ]}

フロイド・ウォーシャルアルゴリズムは、グラフ内の各頂点ペア間の多くの可能なパスを比較します。すべての最短パスを見つけることが保証されており、${\displaystyle \Theta (|V|^{3})}$グラフでの比較、^{[ 1 ] [ 9 ]}たとえ${\displaystyle \Theta (|V|^{2})}$グラフ内のエッジに対して、2つの頂点間の最短経路の推定値を段階的に改善し、推定値が最適になるまで繰り返します。

グラフを考えてみよう${\displaystyle G}$頂点を持つ${\displaystyle V}$1から ${\displaystyle N}$さらに関数について考えてみましょう。${\displaystyle \mathrm {shortestPath} (i,j,k)}$最短経路の長さ（存在する場合）を返します。${\displaystyle i}$に${\displaystyle j}$頂点はセットからのみ使用する${\displaystyle \{1,2,\ldots ,k\}}$途中の地点として。さて、この関数が与えられたとき、私たちの目標は、各地点からの最短経路の長さを求めることです。${\displaystyle i}$それぞれに${\displaystyle j}$任意の頂点を使用して${\displaystyle \{1,2,\ldots ,N\}}$定義上、これは値です${\displaystyle \mathrm {shortestPath} (i,j,N)}$これは再帰的に見つけることになります。

注目してください${\displaystyle \mathrm {shortestPath} (i,j,k)}$以下でなければならない${\displaystyle \mathrm {shortestPath} (i,j,k-1)}$頂点の使用が許可されれば、より柔軟に対応できます。${\displaystyle k}$。 もし${\displaystyle \mathrm {shortestPath} (i,j,k)}$実際にはより少ない${\displaystyle \mathrm {shortestPath} (i,j,k-1)}$そうすれば、${\displaystyle i}$に${\displaystyle j}$頂点を使用して${\displaystyle \{1,2,\ldots ,k\}}$それは、頂点を使用しないそのようなパスよりも短い。${\displaystyle k}$負のサイクルが存在しないため、このパスは次のように分解できます。

（１）${\displaystyle i}$に${\displaystyle k}$頂点を使用する${\displaystyle \{1,2,\ldots ,k-1\}}$、 に続く

（２）${\displaystyle k}$に${\displaystyle j}$頂点を使用する${\displaystyle \{1,2,\ldots ,k-1\}}$。

そしてもちろん、これらは最短経路（あるいは複数の最短経路）でなければなりません。そうでなければ、さらに長さを短くできてしまうからです。言い換えれば、次の漸化式にたどり着きました。

${\displaystyle \mathrm {shortestPath} (i,j,k)=}$

${\displaystyle \mathrm {min} {\Big (}\mathrm {shortestPath} (i,j,k-1),}$

${\displaystyle \mathrm {shortestPath} (i,k,k-1)+\mathrm {shortestPath} (k,j,k-1){\Big )}}$。

基本ケースは次のように与えられる。

${\displaystyle \mathrm {shortestPath} (i,j,0)=w(i,j),}$

どこ${\displaystyle w(i,j)}$は、エッジの重みを表します。${\displaystyle i}$に${\displaystyle j}$存在する場合は 、存在しない場合は ∞ (無限大) となります。

これらの数式はフロイド・ウォーシャルアルゴリズムの中核を成すものです。このアルゴリズムは、まず を計算することによって機能します。${\displaystyle \mathrm {shortestPath} (i,j,k)}$すべての人々のために${\displaystyle (i,j)}$ペア${\displaystyle k=0}$、 それから${\displaystyle k=1}$、 それから${\displaystyle k=2}$など。このプロセスは、${\displaystyle k=N}$そして、私たちはすべての最短経路を見つけました${\displaystyle (i,j)}$任意の中間頂点を用いたペアリング。この基本バージョンの擬似コードを以下に示します。

dist を |V| × |V| の最小距離の配列とし、初期値を ∞ (無限大) と する。各エッジ ( u , v )について、dist [ u ][ v ] = w( u , v ) // エッジ ( u , v )の重みとする。各頂点vについて、 dist[ v ][ v ] = 0 とする。kを1から|V| まで、 iを1から|V| まで、 jを1から|V| までとする。dist [ i ][ j ] > dist[ i ][ k ] + dist[ k ][ j ]の場合、 dist[ i ][ j ] = dist[ i ][ k ] + dist[ k ][ j ] end if

上記のアルゴリズムは、左下のグラフ上で実行されます。

上記でk = 0とラベル付けされた外側ループの最初の再帰の前には、既知のパスはグラフの単一のエッジのみに対応します。k = 1では、頂点 1 を通るパスが見つかります。特に、パス [2,1,3] が見つかり、エッジ数は少ないが (重みの点で) 長いパス [2,3] が置き換えられます。k = 2では、頂点 {1,2} を通るパスが見つかります。赤と青のボックスは、パス [4,2,1,3] が、以前の反復で遭遇した 2 つの既知のパス [4,2] と [2,1,3] からどのように組み立てられるかを示しており、交差部分に 2 が含まれています。パス [4,2,3] は考慮されません。これは、2 から 3 までの最短パスが [2,1,3] であるためです。k = 3では、頂点 {1,2,3} を通るパスが見つかります。最後に、k = 4 の時点で、すべての最短経路が見つかります。

kの各反復における距離行列（更新された距離は太字で示す）は次のようになる。

負のサイクルとは、辺の合計が負の値になるサイクルのことです。どの頂点のペア間にも最短経路は存在しません。${\displaystyle i}$、${\displaystyle j}$これは負のサイクルの一部を形成します。なぜなら、経路の長さは${\displaystyle i}$に${\displaystyle j}$は任意に小さい値（負の値）をとることができます。数値的に意味のある出力を得るために、フロイド・ウォーシャルアルゴリズムは負のサイクルが存在しないことを前提としています。しかし、負のサイクルが存在する場合でも、フロイド・ウォーシャルアルゴリズムを使用してそれらを検出できます。その直感的な説明は次のとおりです。

• フロイド・ウォーシャルアルゴリズムは、すべての頂点ペア間の経路長を繰り返し修正します。${\displaystyle (i,j)}$（以下を含む）${\displaystyle i=j}$;
• 最初は、経路の長さ${\displaystyle (i,i)}$ゼロです。
• 道${\displaystyle [i,k,\ldots ,i]}$長さがゼロ未満、つまり負のサイクルを表す場合にのみ、これを改善できます。
• したがって、アルゴリズムの後、${\displaystyle (i,i)}$負の長さのパスが存在する場合は負になります${\displaystyle i}$戻る${\displaystyle i}$。

したがって、Floyd–Warshallアルゴリズムを使用して負のサイクルを検出するには、パス行列の対角線を調べればよく、負の数が存在する場合は、グラフに少なくとも1つの負のサイクルが含まれていることを示します。^{[ 9 ]}ただし、負のサイクルが存在する場合、アルゴリズムの実行中に指数関数的に大きな数（オーダー）が発生します。${\displaystyle \Omega (6^{n}\cdot w_{max})}$現れる可能性がある${\displaystyle w_{max}}$はグラフ内の最大の絶対値のエッジ重みです。整数アンダーフローの問題を回避するには、アルゴリズムの最も内側の for ループ内で負のサイクルをチェックする必要があります。^{[ 11 ]}

フロイド・ウォーシャルアルゴリズムは通常、すべての頂点ペア間のパスの長さのみを提供します。簡単な修正を加えることで、任意の2つの端点頂点間の実際のパスを再構築する方法を作成できます。各頂点から他のすべての頂点への実際のパスを保存したくなるかもしれませんが、これは必要なく、実際にはメモリの面で非常にコストがかかります。代わりに、最短パスツリーを使用できます。これは、各ノードについて計算できます。${\displaystyle \Theta (|E|)}$時間を使う${\displaystyle \Theta (|V|)}$メモリを使用することで、接続された任意の2つの頂点間の有向パスを効率的に再構築できます。

distを${\displaystyle |V|\times |V|}$最小距離の配列を初期化します${\displaystyle \infty }$（無限） prevを${\displaystyle |V|\times |V|}$nullで初期化された頂点インデックスの配列プロシージャFloydWarshallWithPathReconstruction ()は、各エッジ (u, v)に対して 、dist[u][v] = w(u, v) // エッジ (u, v) の重みを実行します。 prev[u][v] = u 各頂点vについて dist[v][v] = 0 prev[v][v] = v kを1から|V|まで繰り返す// 標準的な Floyd-Warshall 実装 i を1から|V| まで繰り返すj を1から|V| まで繰り返すもしdist[i][j] > dist[i][k] + dist[k][j]ならば dist[i][j] = dist[i][k] + dist[k][j] prev[i][j] = prev[k][j]

手続きPath (u, v)は、 prev[u][v] = nullの場合、 []を返します。 パス = [v] u ≠ vの間、 v = prev[u][v] path.prepend(v) 戻りパス

させて${\displaystyle n}$なれ${\displaystyle |V|}$頂点の数。すべてを見つけるには${\displaystyle n^{2}}$の ${\displaystyle \mathrm {shortestPath} (i,j,k)}$（すべての${\displaystyle i}$そして${\displaystyle j}$） ${\displaystyle \mathrm {shortestPath} (i,j,k-1)}$必要${\displaystyle \Theta (n^{2})}$オペレーション。 ${\displaystyle \mathrm {shortestPath} (i,j,0)=\mathrm {edgeCost} (i,j)}$そして、次のシーケンスを計算します。${\displaystyle n}$行列${\displaystyle \mathrm {shortestPath} (i,j,1)}$、${\displaystyle \mathrm {shortestPath} (i,j,2)}$、${\displaystyle \ldots }$、${\displaystyle \mathrm {shortestPath} (i,j,n)}$それぞれコストは${\displaystyle \Theta (n^{2})}$アルゴリズムの総時間計算量は${\displaystyle n\cdot \Theta (n^{2})=\Theta (n^{3})}$[ ^{9 ] [ 13 ]​}

フロイド・ウォーシャルアルゴリズムは、以下の問題を解決するために使用できます。

• 有向グラフの推移閉包（ウォーシャルのアルゴリズム）。ウォーシャルによるアルゴリズムの元の定式化では、グラフは重み付けされておらず、ブール隣接行列で表されます。そして、加算演算は論理積（AND）に、最小値演算は論理和（OR）に置き換えられます。
• 有限オートマトンによって受理される正規言語を表す正規表現を見つけること（クリーネのアルゴリズム、フロイド・ウォーシャル・アルゴリズムの密接に関連した一般化）^{[ 14 ]}
• 実数行列の逆行列計算（ガウス・ジョルダン法）^{[ 15 ]}
• 最適なルーティング。このアプリケーションでは、2つの頂点間のフローが最大となるパスを見つけることが目的です。つまり、上記の擬似コードのように最小値を取るのではなく、最大値を取るということです。エッジの重みはフローに対する固定制約を表します。パスの重みはボトルネックを表すため、上記の加算演算は最小値演算に置き換えられます。
• パスファインダーネットワークの高速計算。
• 最も広い経路／最大帯域幅の経路
• 差分境界行列（DBM）の標準形の計算
• グラフ間の類似性を計算する
• AND/OR/閾値グラフにおける推移閉包。^{[ 16 ]}

多くのプログラミング言語に対応した実装が利用可能です。

• C++の場合、boost::graphライブラリでは
• C#については、QuikGraphをご覧ください。
• C#の場合は、QuickGraphPCLを参照してください（QuickGraph のフォークで、ポータブルクラスライブラリを使用するプロジェクトとの互換性が向上しています）。
• Javaの場合、Apache Commons Graphライブラリでは
• JavaScriptの場合、Cytoscapeライブラリで
• Juliaの場合、Graphs.jlパッケージでは
• MATLABの場合、Wayback Machineに 2013 年 8 月 17 日にアーカイブされたMatlab_bgl パッケージ
• Perlの場合、Graphモジュールで
• Pythonの場合は、SciPyライブラリ（モジュールscipy.sparse.csgraph）またはNetworkXライブラリを使用します。
• Rの場合、パッケージe1071とRfast
• C言語の場合、pthreadsを使用した並列化実装で、floydWarshall.hにあるデータへのSQLiteインターフェースが含まれています。

非負のエッジ重みを持つグラフの場合、ダイクストラ法は、単一の頂点からすべての最短経路を、実行時間で見つけるために使用できます。${\displaystyle \Theta (|E|+|V|\log |V|)}$したがって、各頂点からダイクストラ法を実行するには時間がかかります。${\displaystyle \Theta (|E||V|+|V|^{2}\log |V|)}$。 以来${\displaystyle |E|=O(|V|^{2})}$これにより、繰り返しダイクストラ法の最悪実行時間は${\displaystyle O(|V|^{3})}$これは、Floyd-Warshall アルゴリズムの漸近的な最悪実行時間と一致するが、関連する定数は非常に重要である。グラフが密である場合(つまり、${\displaystyle |E|\approx |V|^{2}}$）、実際には Floyd-Warshall アルゴリズムの方が優れたパフォーマンスを発揮する傾向があります。グラフが疎な場合 (つまり、${\displaystyle |E|}$よりかなり小さい${\displaystyle |V|^{2}}$) ダイクストラが優勢になる傾向がある。

負の辺は存在するが負のサイクルが存在しない疎グラフの場合、ジョンソンのアルゴリズムを使用でき、その漸近実行時間は反復ダイクストラ法と同じである。

密なグラフにおける全ペア最短経路計算を高速化するために高速行列乗算を使用する既知のアルゴリズムもありますが、これらは通常、エッジの重みに関して追加の仮定（例えば、小さな整数であることを要求するなど）を置きます。 ^{[ 17 ] [ 18 ]}さらに、実行時間に大きな定数係数があるため、非常に大きなグラフの場合にのみ、Floyd–Warshall アルゴリズムよりも高速化されます。

• フロイド・ウォーシャルアルゴリズムのインタラクティブアニメーション
• フロイド・ウォーシャルアルゴリズムのインタラクティブアニメーション（ミュンヘン工科大学）