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

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

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

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

\(u\) から \(v\) への路で通り抜ける頂点の数字が全て \(r\) 以下のものが存在するならば、そのような路の中で最短のものを \(\pi(u, v, r)\) とする。

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

制限された最短路 \(\pi(u, v, r)\) の再帰的構造
図 9.3
制限された最短路 \(\pi(u, v, r)\) の再帰的構造

\(\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)\) の計算です。この再帰方程式も動的計画法のアルゴリズムへと簡単に変換できます:

procedure \(\texttt{KleeneASPS}\)(\(V, E, w\))

for 頂点 \(u\) do

for 頂点 \(v\) do

\(\mathit{dist}[u,v,0] \leftarrow w(u \rightarrow v)\)

for \(r \leftarrow 1\) to \(V\) do

for 頂点 \(u\) do

for 頂点 \(v\) do

if \(\mathit{dist}[u,v,r-1] < \mathit{dist}[u,r,r-1] + \mathit{dist}[r,v,r-1]\) then

\(\mathit{dist}[u,v,r] \leftarrow \mathit{dist}[u,v,r-1]\)

else

\(\mathit{dist}[u,v,r] \leftarrow \mathit{dist}[u,r,r-1] + \mathit{dist}[r,v,r-1]\)

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

procedure \(\texttt{FloydWarshall}\)(\(V, E, w\))

for 頂点 \(u\) do

for 頂点 \(v\) do

\(\mathit{dist}[u,v] \leftarrow w(u \rightarrow v)\)

for 頂点 \(r\) do

for 頂点 \(u\) do

for 頂点 \(v\) do

if \(\mathit{dist}[u,v] < \mathit{dist}[u,r] + \mathit{dist}[r,v]\) then

\(\mathit{dist}[u,v] \leftarrow \mathit{dist}[u,r] + \mathit{dist}[r,v]\)

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


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

広告