Floyd Warshall Algorithm

現在地から目的地までの最短経路の選択に迷っていますか。

Floyd-Warshall のアルゴリズムは、グラフ内のすべてのペアの頂点間の最短経路を見つけるために使用され、グラフ内の各辺には正または負の重みがあります。
このアルゴリズムを使用する最大の利点は、任意の2つの頂点間のすべての最短距離をO（V3）（Vはグラフの頂点数）で計算できることである。
フロイド-ウォーシャル・アルゴリズムは、フロイドのアルゴリズム、ロイ-フロイドのアルゴリズム、ロイ-ウォーシャルのアルゴリズム、WFIアルゴリズムとも呼ばれている。

アルゴリズム

N個の頂点を持つグラフについて：

Step 1: 任意の2頂点間の最短経路を無限大で初期化する。

Step 2: 中間頂点が0のペア最短経路をすべて探し、次に中間頂点が1ある最短経路を探し、そして… N個の頂点すべてを中間ノードとして使用するまで続ける。

ステップ3: 前の操作で得られた任意の2つのペア間の最短経路を最小化する。

ステップ4: 任意の2頂点 (i,j) に対して、実際には最初のK個のノードを使ってこのペア間の距離を最小化する必要があり、最短経路は次のようになる： min(dist+dist,dist).

distは最初のK個の頂点だけを使った最短経路、distはペアk、j間の最短経路を表わします。最短経路はiからkへの最短経路、そしてkからjへの最短経路を連結したものになるため。

for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
dist = min( dist, dist + dist );
}
}
}

与えられたグラフを次のようにする：

以下の手順に従ってすべての頂点の組の間の最短経路を求めることができる．

各セルAはith頂点からjth頂点までの距離で埋め尽くされている。 ith頂点からjth頂点への経路がない場合は、セルは無限大のままです。

2. 今度は行列A0を使って行列A1を作ってみましょう。 1列目、1行目の要素はそのままにしておきます。残りのセルは次のようにして埋める。

送信元から送信先までの最短経路の凍結頂点をkとする。このステップでは、kは第1頂点である。Aは(A + A) if (A > A + A)で埋められる。

つまり、送信元から送信先までの直接距離が頂点kを通る経路より大きい場合、そのセルはA + Aで埋められる。

このステップでは、kは第1頂点である。この頂点kを通る送信元の頂点から送信先の頂点までの距離を計算する。