(Kleene-Roy-) Floyd-Warshall (-Ingerman)

Johnson のアルゴリズムのフィボナッチヒープを使った実装と比べると、高速な方の動的計画法アルゴリズムでさえ最悪ケースの計算時間が \(O(\log V)\) 倍低速です。最短路問題の異なる定式化を使うとこの対数部分を改善できます。この定式化を使ったアルゴリズムは 1962 年に Robert Floyd (ピーター・フロイト) と Peter Ingerman (ピーター・インガーマン) によってぞれぞれ独立に発見され、両者とも同年の前半に Stephen Warshall (ステファン・ワーシャル) によって発表されたアルゴリズムを一般化したと記しています。また正確に言えば、この Warshall のアルゴリズムは 1959 年には Bernand Roy (バーナード・ロイ) によって、そして同じ再帰パターンは 1951 年に Stephen Kleene (スティーヴン・クリーネ)¹ によって発見されています。

Warshall (と Roy と Kleene) は動的計画法の再帰方程式の三つ目のパラメータとして利用できる別の値を提案しました。この新しいパラメータは辺の数を制限するためではなく、通り抜けられる頂点を制限するために使われます。ここで「通り抜ける」とは「頂点に入ってかつ出る」を意味します。例えば \(w \rightarrow x \rightarrow y \rightarrow z\) という路は \(w\) から始まり、\(x, y\) を通り抜け、\(z\) で終わります。

頂点に \(1\) から \(V\) までの数字を適当に割り当てます。任意の頂点の組 \(u, v\) と任意の整数 \(r\) について、\(\pi(u, v, r)\) を次のように定義します:

この定義から \(\pi(u, v, V)\) が \(u\) から \(v\) への真の最短路となります。Kleene と Roy と Warshall は、この路についての単純な再帰的構造を発見しました:

• 路 \(\pi(u, v, 0)\) はどんな頂点も通り抜けることができない。よってこの路は \(u\) から \(v\) への辺だけからなるか、この辺が無ければ存在しない。

• \(r > 0\) について、\(\pi(u, v, r)\) は \(r\) を通り抜けるか通り抜けないかのどちらかである。

  • \(\pi(u, v, r)\) が頂点 \(r\) を通り抜けるならば、この路は \(u\) から \(r\) への部分路とその後に続く \(r\) から \(v\) への部分路の二つに分けることができる。二つの部分路は数字が \(r - 1\) 以下の頂点しか通り抜けず、さらにその条件を満たす路の中で最小のものだから、これらの部分路は \(\pi(u, r, r-1)\) と \(\pi(r, v, r-1)\) である。

  • そうでなく、路 \(\pi(u, r, v)\) が頂点 \(r\) を通り抜けない場合、この路は数字が \(r - 1\) 以下の頂点しか通り抜けず、かつそのような路の中で最短のものである。したがって \(\pi(u, v, r) = \pi(u, v, r-1)\) である。

\(\mathit{dist}(u, v, r)\) で \(\pi(u, v, r)\) の長さを表すことにすると、\(\pi(u, v, r)\) の再帰的な構造から直ちに次の再帰方程式が得られます: \[ \mathit{dist}(u, v, r) = \begin{cases} w(u \rightarrow v) & \text{if } r = 0 \\ \min \left\lbrace \begin{array}{c} \mathit{dist}(u, v, r-1) \\ \min (\mathit{dist}(u, r, r-1) + \mathit{dist}(r, v, r-1)) \end{array} \right\rbrace & \text{それ以外} \end{cases} \]

問題を解くために必要なのは、全ての頂点の組 \(u, v\) に対する \(\mathit{dist}(u, v, V)\) の計算です。この再帰方程式も動的計画法のアルゴリズムへと簡単に変換できます:

これまでに見てきた最短路問題に対する動的計画法のアルゴリズムと同じように、\(\textsc{KleeneASPS}\) もメモ配列の最後の次元を削除することで単純化できます。また頂点の番号付けは任意であることから、疑似コードにおいて番号を具体的に取得する必要はありません。これで、Floyd が改善した形の Warshall のアルゴリズムが手に入ります:

\(\textsc{FloydWarshall}\) と先述の少し遅い動的計画法アルゴリズム \(\textsc{LeyzorekAPSP}\) を比較すると興味深いことが分かります。\(\textsc{LeyzorekAPSP}\) では全ての頂点の三つ組を \(O(\log V)\) 回反復するのに対して \(\textsc{FloydWarshall}\) では一度の反復で済むのですが、二つのアルゴリズムの違いはループの順番だけなのです！

1. 発音は「cley nee (クレイニ)」です。「clean (クリーン)」、「clean-ee (クリー二)」、「clay-nuh (クレイナ)」、「dimaggio (ディマジオ)」は全て間違っています [訳注: 日本語では「クリーネ」と呼ばれますが、これも間違いです]。彼は任意の有限オートマトンに対応する正規表現が存在することを帰納法を使って証明しており、その帰納法のパターンが Floyd-Warshall の再帰方程式と本質的に同じです。^[return]