ワーシャル?フロイド法（英: Floyd?Warshall Algorithm）は、重み付き有向グラフの全ペアの最短経路問題を多項式時間で解くアルゴリズムである。名称は考案者であるスティーブン・ワーシャル（英語版）とロバート・フロイドにちなむ（2人はそれぞれ独立に考案）。フロイドのアルゴリズム、ワーシャルのアルゴリズム、フロイド?ワーシャル法とも呼ばれる。
概要

ワーシャル?フロイド法の概略は以下の通りである：

入力：

(有向または無向)グラフ G = ( V , E ) {\displaystyle G=(V,E)}

E {\displaystyle E} の各辺の長さ


出力：頂点 i {\displaystyle i} と頂点 j {\displaystyle j} を結ぶ最短経路を全ての i , j ∈ V {\displaystyle i,j\in V} に対して出力

計算量： O ( V 3 ) {\displaystyle O(V^{3})}

アイデア

簡単の為 V = 1 , . . . , n {\displaystyle V={1,...,n}} 上のグラフ G = ( V , E ) {\displaystyle G=(V,E)} のみを考える。

k {\displaystyle k} を n {\displaystyle n} 以下の整数とし、 K = 1 , . . . , k {\displaystyle K={1,...,k}} とする。 G {\displaystyle G} の 各頂点 i , j {\displaystyle i,j} に対し、 G {\displaystyle G} を K ∪ { i , j } {\displaystyle K\cup \{i,j\}} に制限したグラフ上での i {\displaystyle i} から j {\displaystyle j} への最短経路を p i , j {\displaystyle p_{i,j}} とする。(経路が無い場合は p i , j = {\displaystyle p_{i,j}=} 「なし」とする。) K ′ = 1 , . . . , k + 1 {\displaystyle K'={1,...,k+1}} とし、 G {\displaystyle G} を K ′ ∪ { i , j } {\displaystyle K'\cup \{i,j\}} に制限したグラフ上での i {\displaystyle i} から j {\displaystyle j} への最短経路を p i , j ′ {\displaystyle p'_{i,j}} とする。 K ′ ∪ { i , j } {\displaystyle K'\cup \{i,j\}} 内での i {\displaystyle i} から j {\displaystyle j} への最短経路は、 k + 1 {\displaystyle k+1} を経由するか、あるいは K ∪ { i , j } {\displaystyle K\cup \{i,j\}} 内にあるかのいずれかであるので、次が成立することが分かる。ただしここで記号「 p 。 。 q {\displaystyle p||q} 」は「経路 p {\displaystyle p} を進んだ後に経路 q {\displaystyle q} を進む」という経路を表す。

p i , j ′ = p i , k + 1 。 。 p k + 1 , j {\displaystyle p'_{i,j}=p_{i,k+1}||p_{k+1,j}}  : p i , k + 1 。 。 p k + 1 , j {\displaystyle p_{i,k+1}||p_{k+1,j}} が p i , j {\displaystyle p_{i,j}} より短い場合

p i , j ′ = p i , j {\displaystyle p'_{i,j}=p_{i,j}}  : そうでない場合。

よって K = 1 , . . . , k {\displaystyle K={1,...,k}} に対する最短経路 p i , j {\displaystyle p_{i,j}} が全ての i , j {\displaystyle i,j} に対して分かっていれば、 K ′ = 1 , . . . , k + 1 {\displaystyle K'={1,...,k+1}} に対する最短経路 p i , j ′ {\displaystyle p'_{i,j}} が全ての i , j {\displaystyle i,j} に対して求まる。

ワーシャル?フロイド法は以上の考察に基づいたアルゴリズムで、 K {\displaystyle K} を空集合に初期化後、 K {\displaystyle K} に頂点 1 , 2 , . . . , n {\displaystyle 1,2,...,n} を付け加えていくことで G = ( V , E ) {\displaystyle G=(V,E)} 上の最短経路を全ての i , j {\displaystyle i,j} に対して求める。

K {\displaystyle K} が空集合の場合、 K ∪ { i , j } = { i , j } {\displaystyle K\cup \{i,j\}=\{i,j\}} 上の i {\displaystyle i} と j {\displaystyle j} を結ぶ最短経路は明らかに次のようになる。ただし簡単の為、各頂点 i , j {\displaystyle i,j} に対し、 i {\displaystyle i} と j {\displaystyle j} を結ぶ辺は多くとも一本としている： i , j {\displaystyle i,j} を結ぶ辺 e {\displaystyle e} があれば、最短経路は e {\displaystyle e} .そうでなければ i {\displaystyle i} と j {\displaystyle j} を結ぶ経路は K ∪ { i , j } {\displaystyle K\cup \{i,j\}} にはそもそも存在しない。

したがってワーシャル?フロイド法では、 p i , j {\displaystyle p_{i,j}} を上述のルールで e {\displaystyle e} もしくは「なし」に初期化した後、前述の方法で G = ( V , E ) {\displaystyle G=(V,E)} 上の最短経路を全ての i , j {\displaystyle i,j} に対して求める。