ワーシャル–フロイド法の概略は以下の通りである: 入力: (有向または無向)グラフ の各辺の長さ 出力:頂点 と頂点 を結ぶ最短経路を全ての に対して出力 計算量: 簡単の為 上のグラフ のみを考える。 を 以下の整数とし、 とする。 の 各頂点 に対し、 を に制限したグラフ上での から への最短経路を とする。(経路が無い場合は 「なし」とする。) とし、 を に制限したグラフ上での から への最短経路を とする。 内での から への最短経路は、 を経由するか、あるいは 内にあるかのいずれかであるので、 次が成立することが分かる。ただしここで記号「」は「経路 を進んだ後に経路 を進む」という経路を表す。 : が より短い場合 : そうでない場合。 よって に対する最短経路 が全ての に対して分かっていれば、 に対する最短経路 が全ての に対して求まる。 ワーシャル–フロイド法は以上の考
![ワーシャル–フロイド法 - Wikipedia](https://cdn-ak-scissors.b.st-hatena.com/image/square/e7379d14529f780137be504ea6c5558e3dc39974/height=288;version=1;width=512/https%3A%2F%2Fupload.wikimedia.org%2Fwikipedia%2Fcommons%2Fthumb%2F7%2F72%2FMax_paraboloid.svg%2F150px-Max_paraboloid.svg.png)