algorithm
Floyd-Warshallアルゴリズム

オールペア最短パスアルゴリズム

Floyd-Warshallのアルゴリズムは、正または負のエッジ重みを持つ重み付きグラフの最短経路を見つけるためのアルゴリズムです。アルゴリズムを1回実行すると、すべての頂点ペア間の最短パスの長さ（合計ウェイト）が求められます。わずかなバリエーションで、最短パスを印刷し、グラフ内の負のサイクルを検出することができます。 Floyd-Warshallはダイナミックプログラミングアルゴリズムです。

例を見てみましょう。このグラフにFloyd-Warshallのアルゴリズムを適用します：

まず、2D行列を2つ取ります。これらは隣接行列です。行列のサイズは、頂点の総数になります。私たちのグラフでは、 4 * 4行列を取ります。 距離行列は、これまでに2つの頂点の間で見つかった最小距離を格納します。まず、エッジを、UVおよび距離/重量の間にエッジが存在する場合は、wは 、我々は、保存されます： distance[u][v] = w 。存在しないすべての辺について、 無限を置くつもりです。 Path Matrixは、2つの頂点間の最短距離パスを再生成するためのものです。最初は、 uとvの間にパスがある場合は、 path[u][v] = uます。つまり、 頂点-vから頂点 -vに来る最善の方法は、 vとuを結ぶエッジを使うことです。 2つの頂点の間にパスがない場合は、ここにNを入れて、現在利用可能なパスがないことを示します。グラフの2つの表は次のようになります。

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  1  |  2  |  3  |  4  |            |     |  1  |  2  |  3  |  4  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  1  |  0  |  3  |  6  |  15 |            |  1  |  N  |  1  |  1  |  1  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  2  | inf |  0  | -2  | inf |            |  2  |  N  |  N  |  2  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  3  | inf | inf |  0  |  2  |            |  3  |  N  |  N  |  N  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  4  |  1  | inf | inf |  0  |            |  4  |  4  |  N  |  N  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
            distance                                     path

ループがないので、対角線はNに設定されます。頂点自体からの距離は0です。

Floyd-Warshallアルゴリズムを適用するために、中間頂点kを選択します。次に、各頂点iについて 、 iからkへ 、次にkからjへ行くことができるかどうかを調べる。ここで、 jは別の頂点であり、 iからjへ行くコストを最小限に抑える。現在の距離[i] [j]が距離[i] [k] + 距離[k] [j]より大きい場合、 距離[i] [j]をこれら2つの距離の合計に等しくします。そして、 経路[i] [j]は経路[k] [j]に設定されます .iからkへ、そしてkからjへ行く方が良いでしょう。すべての頂点がkとして選択されます。私たちは、3つのネストされたループがあるでしょう：kは 1から4に行くために、iは 1から4まで行くとjは我々がチェックつもり1から4に行きます：

if distance[i][j] > distance[i][k] + distance[k][j]
    distance[i][j] := distance[i][k] + distance[k][j]
    path[i][j] := path[k][j]
end if

基本的に調べているのは、 頂点のすべてのペアについて、別の頂点を通ることでより短い距離を得ることですか？グラフの操作の合計数は4 * 4 * 4 = 64になります。これは、この検査を64回行うつもりであることを意味します。それらのいくつかを見てみましょう：

距離よりも大きくない場合、K = 1、I = 2及びJ = 3、 距離[i] [j]が -2であり、[I] [K] + 距離[K] [J] = -2 + 0 = -2 。それで変わらないでしょう。再び、k = 1 の場合、I = 4、J = 2、 距離[i] [j]が 距離よりも大きい無限 = [I] [K] + 距離[K] [J] = 1 + 3 = 4 。そこで、 distance [i] [j] = 4を入れ、 path [i] [j] = path [k] [j] = 1を入れます。これが意味することは、 頂点4から頂点2に行くためには、経路4-> 1-> 2が既存の経路よりも短いことである。これは、両方の行列をどのように埋め込むかです。各ステップの計算をここに示します 。必要な変更を加えた後の行列は次のようになります。

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  1  |  2  |  3  |  4  |            |     |  1  |  2  |  3  |  4  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  1  |  0  |  3  |  1  |  3  |            |  1  |  N  |  1  |  2  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  2  |  1  |  0  | -2  |  0  |            |  2  |  4  |  N  |  2  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  3  |  3  |  6  |  0  |  2  |            |  3  |  4  |  1  |  N  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  4  |  1  |  4  |  2  |  0  |            |  4  |  4  |  1  |  2  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
            distance                                     path

これは最短距離行列です。例えば、 1から4までの最短距離は3であり、 4から3までの最短距離は2である 。私たちの疑似コードは次のようになります：

Procedure Floyd-Warshall(Graph):
for k from 1 to V     // V denotes the number of vertex
    for i from 1 to V
       for j from 1 to V
           if distance[i][j] > distance[i][k] + distance[k][j]
               distance[i][j] := distance[i][k] + distance[k][j]
               path[i][j] := path[k][j]
           end if
       end for
    end for
end for

パスの印刷：

パスを印刷するには、 パスマトリックスをチェックします。 uからvへのパスを印刷するには、 パス[u] [v]から開始します 。私たちは、スタック内の[V] [U]我々はパス[U]を見つけるまで[V] = U、V = パス[U] [V]を変え続ける設定とパスのすべての値をプッシュします。 Uを見つけた後、私たちは、Uを印刷し、スタックから項目を飛び出る開始し、それらを印刷します。これは、 パス行列が他のノードからのvへの最短経路を共有する頂点の値を格納するためである。疑似コードは次のようになります。

Procedure PrintPath(source, destination):
s = Stack()
S.push(destination)
while Path[source][destination] is not equal to source
    S.push(Path[source][destination])
    destination := Path[source][destination]
end while
print -> source
while S is not empty
    print -> S.pop
end while

負のエッジサイクルを見つける：

負のエッジサイクルがあるかどうかを調べるには、 距離行列の主対角をチェックする必要があります。対角線の値が負の場合、グラフに負のサイクルがあることを意味します。

複雑：

ワーシャル-フロイド法の複雑さはO（V³）であり、空間の複雑さがある：O（V²）。