ワーシャル–フロイド法
G = ( V , E ) {\displaystyle G=(V,E)} において p i , j {\displaystyle p_{i,j}} 上にある全ての辺を順に赤く塗っていく、という作業を全ての i , j {\displaystyle i,j} に対して繰り返し、最終的に赤くなった辺を集めることでできる G = ( V , E ) {\displaystyle G=(V,E)} の部分グラフを P {\displaystyle P} とする。 P {\displaystyle P} さえあれば、 p i , j {\displaystyle p_{i,j}} を全て復元できる。 したがってワーシャル-フロイド法では { p i , j } i , j ∪ { 1 , . . . , n } {\displaystyle \{p_{i,j}\}_{i,j\cup \{1,...,n\}}} を全て記憶しなくても P {\displaystyle P} のみを記憶しておけばよい。 (ただし P {\displaystyle P} から p i , j {\displaystyle p_{i,j}} を復元するのに計算量が必要であるため、計算量が増えてしまう。 なお適切に経路 p i , j {\displaystyle p_{i,j}} を選べば P {\displaystyle P} は木になるので、このことを利用すれば復元にかかる計算量もある程度押さえられる。)
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} に対して求める。
ワーシャル–フロイド法は以下のような問題を解くのに利用可能である:
有向グラフでの最短経路を求める(フロイドのアルゴリズム)。この場合、全エッジの重みを同じ正の値に設定する。通常、1 を設定するので、ある経路の重みはその経路上にあるエッジの数を表す。
有向グラフでの推移閉包を求める(ワーシャルのアルゴリズム)。スティーブン・ワーシャルの元々のアルゴリズムでは、重みなしのグラフであり、ブーリアンの隣接行列が使用されていた。そのため、加算の代わりに論理積(AND)が使われ、最小を求めるには論理和(OR)が使用されていた。
ある有限オートマトンにより受容される正規言語を記述する正規表現を探す(クリーネのアルゴリズム)。
実数の行列の逆行列を求める(Gauss-Jordan elimination)。
最適ルーティング。ネットワーク上の2つのノード間で通信量が最大な経路を求めるといった用途がある。そのためには上掲の擬似コードのように最小を求めるのではなく最大を求めるようにする。エッジの重みは通信量の上限を表す。経路の重みはボトルネックによって決まる。したがって上掲の擬似コードでの加算操作は最小を求める操作に置き換えられる。
簡単の為 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}} とする。