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

フロイド・ワーシャルアルゴリズム
クラス	全ペア最短経路問題（重み付きグラフの場合）
データ構造	グラフ
最悪の場合のパフォーマンス	Θ （ \| V \| 3 ） {\displaystyle \Theta (\|V\|^{3})}
最高のパフォーマンス	Θ （ \| V \| 3 ） {\displaystyle \Theta (\|V\|^{3})}
平均的なパフォーマンス	Θ （ \| V \| 3 ） {\displaystyle \Theta (\|V\|^{3})}
最悪の場合の空間複雑度	Θ （ \| V \| 2 ） {\displaystyle \Theta (\|V\|^{2})}

グラフ理論におけるアルゴリズム

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

歴史と命名

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

アルゴリズム

フロイド・ワーシャルアルゴリズムは、グラフ上の各頂点ペア間の多数の可能な経路を比較します。このアルゴリズムはすべての最短経路を見つけることが保証されており、グラフ内に辺が存在する場合でも、グラフ内の比較を用いてこれを行うことができます^[1]^[9]。このアルゴリズムは、2つの頂点間の最短経路の推定値を段階的に改善し、推定値が最適になるまで改善していきます。 $\Theta (|V|^{3})$ $\Theta (|V|^{2})$

1からまで番号が付けられた頂点を持つグラフを考えます。さらに、集合に含まれる頂点のみを途中の点として用いて、からへの最短経路（存在する場合）の長さを返す関数を考えます。この関数が与えられた場合、内の任意の頂点を用いて、各から各への最短経路の長さを求めることが目標となります。定義により、これはという値であり、を再帰的にとして求めます。 $G$ $V$ $N$ $\mathrm {shortestPath} (i,j,k)$ $i$ $j$ $\{1,2,\ldots ,k\}$ $i$ $j$ $\{1,2,\ldots ,N\}$ $\mathrm {shortestPath} (i,j,N)$

はより小さいか等しい必要があることに注意してください。頂点を使用できる場合、より柔軟に対応できます。がより小さい場合、頂点を使用しない経路よりも短い、頂点を使用するからへの経路が存在するはずです。負の閉路が存在しないため、この経路は次のように分解できます。 $\mathrm {shortestPath} (i,j,k)$ $\mathrm {shortestPath} (i,j,k-1)$ $k$ $\mathrm {shortestPath} (i,j,k)$ $\mathrm {shortestPath} (i,j,k-1)$ $i$ $j$ $\{1,2,\ldots ,k\}$ $k$

（１）頂点からまでのパス。

i

k

\{1,2,\ldots ,k-1\}

（２）頂点を利用するからへの経路。

k

j

\{1,2,\ldots ,k-1\}

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

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

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

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

。

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

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

ここで、は、存在する場合はからへのエッジの重みを表し、そうでない場合は ∞ (無限大) を表します。 $w(i,j)$ $i$ $j$

これらの式はフロイド・ワーシャル法の核心です。このアルゴリズムは、まずのすべてのペアについてを計算し、次に、そして、というように繰り返します。このプロセスはまで続き、中間頂点を介さずにすべてのペアの最短経路が求まります。この基本版の擬似コードを以下に示します。 $\mathrm {shortestPath} (i,j,k)$ $(i,j)$ $k=0$ $k=1$ $k=2$ $k=N$ $(i,j)$

擬似コード

dist を、
各辺 ( u、v )に対して ∞ (無限大) に初期化された最小距離の |V| × |V| 配列とします
    。dist[ u ][ v ] = w( u、v )  を実行します。//各頂点vに対する辺 ( u 、 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 ]
            終了

注：フロイド・ワーシャルアルゴリズムの実装においてよくある間違いは、三重にネストされたループの順序を間違えることです（正しい順序はですKIJ）。誤ったIJKとのIKJアルゴリズムは、インスタンスによっては正しい解を得られません。しかし、これらを3回繰り返すと正しい解が得られることが証明できます。^[10]

例

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

$上記でk = 0$ とラベル付けされた外側のループの最初の再帰の前は、グラフ内の単一のエッジに対応する既知のパスのみが存在します。 $k = 1$ では、頂点 1 を通過するパスが見つかります。具体的には、エッジは少ないがより長い (重みの点で) パス [2,3] を置き換えるパス [2,1,3] が見つかります。 $k = 2$ では、頂点 {1,2} を通過するパスが見つかります。赤と青のボックスは、以前の反復で検出された 2 つの既知のパス [4,2] と [2,1,3] から、交差点に 2 がある状態で、パス [4,2,1,3] が組み立てられる様子を示しています。パス [4,2,3] は考慮されません。なぜなら、[2,1,3] は 2 から 3 へのこれまでに検出された最短パスだからです。 $k = 3$ では、頂点 {1,2,3} を通過するパスが見つかります。最後に、 $k = 4$ で、すべての最短経路が見つかります。

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


$k = 0$		1	2	3	4
$k = 0$		$j$
$私$	1	0	∞	−2	∞
	2	4	0	3	∞
	3	∞	∞	0	2
	4	∞	−1	∞	0


$k = 1$		1	2	3	4
$k = 1$		$j$
$私$	1	0	∞	−2	∞
	2	4	0	2	∞
	3	∞	∞	0	2
	4	∞	−1	∞	0


$k = 2$		1	2	3	4
$k = 2$		$j$
$私$	1	0	∞	−2	∞
	2	4	0	2	∞
	3	∞	∞	0	2
	4	3	−1	1	0


$k = 3$		1	2	3	4
$k = 3$		$j$
$私$	1	0	∞	−2	0
	2	4	0	2	4
	3	∞	∞	0	2
	4	3	−1	1	0


$k = 4$		1	2	3	4
$k = 4$		$j$
$私$	1	0	−1	−2	0
	2	4	0	2	4
	3	5	1	0	2
	4	3	−1	1	0

負のサイクルを伴う行動

負の閉路とは、辺の和が負の値となる閉路のことです。負の閉路を構成する任意の頂点ペア間には最短経路は存在しません。これは、からまでの経路長が任意に小さい（負の値）可能性があるためです。数値的に意味のある出力を得るために、フロイド・ワーシャルアルゴリズムは負の閉路が存在しないものと仮定します。しかしながら、負の閉路が存在する場合、フロイド・ワーシャルアルゴリズムを用いてそれを検出することができます。その直感的な説明は以下のとおりです。 $i$ $j$ $i$ $j$

フロイド・ワーシャルアルゴリズムは、を含むすべての頂点ペア間のパスの長さを反復的に修正します。 $(i,j)$ $i=j$
最初は、パスの長さはゼロです。 $(i,i)$
パスの長さが 0 未満の場合、つまり負のサイクルを表す場合にのみ、パスはこれを改善できます。 $[i,k,\ldots ,i]$
したがって、アルゴリズムの実行後、からに戻る負の長さのパスが存在する場合、は負になります。 $(i,i)$ $i$ $i$

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

パス再構築

フロイド・ワーシャルアルゴリズムは通常、すべての頂点ペア間の経路の長さのみを提供します。簡単な変更を加えることで、任意の2つの端点間の実際の経路を再構築する手法を作成できます。各頂点から他の各頂点への実際の経路を保存したいと考えるかもしれませんが、これは必須ではなく、実際にはメモリ消費量が非常に多くなります。代わりに、最短経路木を使用できます。最短経路木は、各ノードについてメモリを使用して時間内に計算でき、接続された任意の2つの頂点間の有向経路を効率的に再構築できます。 $\Theta (|E|)$ $\Theta (|V|)$

擬似コード

配列はからへprev[u][v]の経路上の最後から2番目の頂点を保持します（の場合は、に自己ループがない場合でも常にが含まれます）。^[12]uvprev[v][v]vv

distを（無限大）
に初期化された最小距離の配列とし、prevをnullに初期化された頂点インデックスの配列とする $|V|\times |V|$  $\infty$  $|V|\times |V|$ 

手順 FloydWarshallWithPathReconstruction ()は、
    各エッジ (u, v)に対して
        、dist[u][v] = w(u, v)  を実行します// エッジ (u, v) の重み
        前[u][v] = u
    各頂点vに対して
        距離[v][v] = 0
        前[v][v] = v
    for k from 1 to |V| do  // 標準のフロイド・ワーシャル実装
        for i from 1 to |V|
             for j from 1 to |V|
                 if dist[i][j] > dist[i][k] + dist[k][j] then
                    分布[i][j] = 分布[i][k] + 分布[k][j]
                    前[i][j] = 前[k][j]

手順 Path (u, v)は、
     prev[u][v] = nullの場合は
        []を返す
    パス = [v]
     u ≠ v の場合
        v = 前[u][v]
        パス.prepend(v)
    戻り経路

時間計算量

を頂点の数とする。の頂点から（すべてのとに対して）をすべて見つけるには、の操作が必要である。から始めて、のコストを持つ行列の列、、、を計算するので、アルゴリズム全体の計算時間はとなる。^[9]^[13] $n$ $|V|$ $n^{2}$ $\mathrm {shortestPath} (i,j,k)$ $i$ $j$ $\mathrm {shortestPath} (i,j,k-1)$ $\Theta (n^{2})$ $\mathrm {shortestPath} (i,j,0)=\mathrm {edgeCost} (i,j)$ $n$ $\mathrm {shortestPath} (i,j,1)$ $\mathrm {shortestPath} (i,j,2)$ $\ldots$ $\mathrm {shortestPath} (i,j,n)$ $\Theta (n^{2})$ $n\cdot \Theta (n^{2})=\Theta (n^{3})$

応用と一般化

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

有向グラフの推移閉包（ワーシャルのアルゴリズム）。ワーシャルによるこのアルゴリズムの元の定式化では、グラフは重み付けされておらず、ブール隣接行列で表されます。そして、加算演算は論理積（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-08-17アーカイブのMatlab_bglパッケージ内
Perlの場合、Graphモジュール
Pythonの場合、SciPyライブラリ（モジュールscipy.sparse.csgraph）またはNetworkXライブラリ
Rの場合、パッケージe1071およびRfast
Cの場合、並列化されたpthreads実装には、floydWarshall.h のデータへのSQLiteインターフェースが含まれています。

他の最短経路アルゴリズムとの比較

非負の辺の重みを持つグラフでは、ダイクストラ法を使って、実行時間で単一の頂点からすべての最短経路を見つけることができます。したがって、各頂点からダイクストラ法を実行すると、の時間がかかります。であるため、繰り返しダイクストラ法の最悪ケースの実行時間はになります。これはフロイド・ワーシャル法の漸近的な最悪ケースの実行時間と一致しますが、関係する定数が非常に重要です。グラフが密な場合（など）、フロイド・ワーシャル法の方が実際にはパフォーマンスが良い傾向があります。グラフが疎な場合（がよりも大幅に小さい場合）、ダイクストラ法が優位になる傾向があります。 $\Theta (|E|+|V|\log |V|)$ $\Theta (|E||V|+|V|^{2}\log |V|)$ $|E|=O(|V|^{2})$ $O(|V|^{3})$ $|E|\approx |V|^{2}$ $|E|$ $|V|^{2}$

負のエッジを持ち負のサイクルを持たないスパースグラフの場合、反復ダイクストラ法と同じ漸近実行時間でジョンソンのアルゴリズムを使用できます。

高速行列乗算を用いて稠密グラフにおける全ペア最短経路計算を高速化するアルゴリズムも知られているが、これらは通常、辺の重みについて追加の仮定（例えば、小さな整数であることを要求するなど）を行っている。 ^[17]^[18]さらに、実行時間における定数係数が大きいため、非常に大きなグラフに対してのみ、フロイド・ワーシャルアルゴリズムよりも高速化される。

参考文献

^ ab コーメン、トーマス H. ;チャールズ・E・ライザーソン;リベスト、ロナルド L. (1990)。アルゴリズム入門(第 1 版)。 MIT プレスとマグロウヒル。ISBN 0-262-03141-8。特に、セクション 26.2「フロイド-ワーシャルアルゴリズム」(p. 558–565) とセクション 26.4「有向グラフのパス問題を解くための一般的なフレームワーク」(p. 570–576) を参照してください。
^ ケネス・H・ローゼン (2003). 『離散数学とその応用第5版』アディソン・ウェスレー. ISBN 978-0-07-119881-3。
^ フロイド, ロバート・W. (1962年6月). 「アルゴリズム97：最短経路」. Communications of the ACM . 5 (6): 345. doi : 10.1145/367766.368168 . S2CID 2003382.
^ ロイ、バーナード(1959). 「トランジビテとコネクシテ」。CRアカデミー。科学。パリ（フランス語）。249：216～ 218
^ ウォーシャル、スティーブン（1962年1月）「ブール行列に関する定理」Journal of the ACM . 9 (1): 11– 12. doi : 10.1145/321105.321107 . S2CID 33763989.
^ Weisstein, Eric W.「フロイド・ワーシャルアルゴリズム」。MathWorld。
^ Kleene, SC (1956). 「神経網と有限オートマトンにおけるイベントの表現」. C.E. Shannon , J. McCarthy (編).オートマトン研究. プリンストン大学出版局. pp. 3– 42.
^ インガーマン, ピーター Z. (1962年11月). 「アルゴリズム141：パスマトリックス」. Communications of the ACM . 5 (11): 556. doi : 10.1145/368996.369016 . S2CID 29010500.
^ abc Hochbaum, Dorit (2014). 「セクション8.9：すべてのペアの最短経路に対するフロイド・ワーシャルアルゴリズム」（PDF） . IEOR 266「グラフアルゴリズムとネットワークフロー」の講義ノート.カリフォルニア大学バークレー校、産業工学・オペレーションズリサーチ学部. pp. 41– 42.
^ Hide, Ikumi (2019). 「フロイド-ワーシャルアルゴリズムの誤った実装は、3回の繰り返しで正しい解を与える」arXiv : 1904.01210 [cs.DS].
^ Stefan Hougardy (2010年4月). 「負の閉路を持つグラフ上のフロイド・ワーシャルアルゴリズム」. Information Processing Letters . 110 ( 8–9 ): 279– 281. doi :10.1016/j.ipl.2010.02.001.
^ 「無料アルゴリズムブック」。
^ Baras, John; Theodorakopoulos, George (2022).ネットワークにおけるパス問題. Springer International Publishing. ISBN 9783031799839。
^ Gross, Jonathan L.; Yellen, Jay (2003). グラフ理論ハンドブック. 離散数学とその応用. CRC Press. p. 65. ISBN 9780203490204。。
^ Peñaloza, Rafael. 「推移閉包のための代数構造」.セミナー「グラフアルゴリズム」 . ドレスデン工科大学、コンピュータサイエンス学部、理論コンピュータサイエンス研究所. 2009年10月22日時点のオリジナルよりアーカイブ。
^ Gillies, Donald (1993). AND/OR優先順位制約を用いたタスクのスケジューリング（博士論文、付録B）（PDF）（レポート）。
^ Zwick, Uri (2002年5月). 「ブリッジングセットと長方形行列乗算を用いた全ペア最短経路」. Journal of the ACM . 49 (3): 289– 317. arXiv : cs/0008011 . doi :10.1145/567112.567114. S2CID 1065901.。
^ Chan, Timothy M. (2010年1月). 「重み付きグラフにおける全ペア最短経路のためのさらなるアルゴリズム」. SIAM Journal on Computing . 39 (5): 2075– 2089. CiteSeerX 10.1.1.153.6864 . doi :10.1137/08071990x. 。

外部リンク

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

[:0-1] コーメン、トーマス H. ;チャールズ・E・ライザーソン;リベスト、ロナルド L. (1990)。アルゴリズム入門(第 1 版)。 MIT プレスとマグロウヒル。ISBN 0-262-03141-8。特に、セクション 26.2「フロイド-ワーシャルアルゴリズム」(p. 558–565) とセクション 26.4「有向グラフのパス問題を解くための一般的なフレームワーク」(p. 570–576) を参照してください。

[2] ケネス・H・ローゼン (2003). 『離散数学とその応用第5版』アディソン・ウェスレー. ISBN 978-0-07-119881-3。

[3] フロイド, ロバート・W. (1962年6月). 「アルゴリズム97：最短経路」. Communications of the ACM . 5 (6): 345. doi : 10.1145/367766.368168 . S2CID 2003382.

[4] ロイ、バーナード(1959). 「トランジビテとコネクシテ」。CRアカデミー。科学。パリ（フランス語）。249：216～ 218

[5] ウォーシャル、スティーブン（1962年1月）「ブール行列に関する定理」Journal of the ACM . 9 (1): 11– 12. doi : 10.1145/321105.321107 . S2CID 33763989.

[6] Weisstein, Eric W.「フロイド・ワーシャルアルゴリズム」。MathWorld。

[7] Kleene, SC (1956). 「神経網と有限オートマトンにおけるイベントの表現」. C.E. Shannon , J. McCarthy (編).オートマトン研究. プリンストン大学出版局. pp. 3– 42.

[8] インガーマン, ピーター Z. (1962年11月). 「アルゴリズム141：パスマトリックス」. Communications of the ACM . 5 (11): 556. doi : 10.1145/368996.369016 . S2CID 29010500.

[:1-9] Hochbaum, Dorit (2014). 「セクション8.9：すべてのペアの最短経路に対するフロイド・ワーシャルアルゴリズム」（PDF） . IEOR 266「グラフアルゴリズムとネットワークフロー」の講義ノート.カリフォルニア大学バークレー校、産業工学・オペレーションズリサーチ学部. pp. 41– 42.

[10] Hide, Ikumi (2019). 「フロイド-ワーシャルアルゴリズムの誤った実装は、3回の繰り返しで正しい解を与える」arXiv : 1904.01210 [cs.DS].

[11] Stefan Hougardy (2010年4月). 「負の閉路を持つグラフ上のフロイド・ワーシャルアルゴリズム」. Information Processing Letters . 110 ( 8–9 ): 279– 281. doi :10.1016/j.ipl.2010.02.001.

[12] 「無料アルゴリズムブック」。

[13] Baras, John; Theodorakopoulos, George (2022).ネットワークにおけるパス問題. Springer International Publishing. ISBN 9783031799839。

[14] Gross, Jonathan L.; Yellen, Jay (2003). グラフ理論ハンドブック. 離散数学とその応用. CRC Press. p. 65. ISBN 9780203490204。。

[15] Peñaloza, Rafael. 「推移閉包のための代数構造」.セミナー「グラフアルゴリズム」 . ドレスデン工科大学、コンピュータサイエンス学部、理論コンピュータサイエンス研究所. 2009年10月22日時点のオリジナルよりアーカイブ。

[16] Gillies, Donald (1993). AND/OR優先順位制約を用いたタスクのスケジューリング（博士論文、付録B）（PDF）（レポート）。

[17] Zwick, Uri (2002年5月). 「ブリッジングセットと長方形行列乗算を用いた全ペア最短経路」. Journal of the ACM . 49 (3): 289– 317. arXiv : cs/0008011 . doi :10.1145/567112.567114. S2CID 1065901.。

[18] Chan, Timothy M. (2010年1月). 「重み付きグラフにおける全ペア最短経路のためのさらなるアルゴリズム」. SIAM Journal on Computing . 39 (5): 2075– 2089. CiteSeerX 10.1.1.153.6864 . doi :10.1137/08071990x. 。