Skip to content →

Floyd-Warshall のアルゴリズム

\(n\) 頂点重み付き有向グラフ \(G\) が与えられたとする。このとき、全頂点間の最短道の長さを \(O(n^3)\) で計算する Floyd-Warshall(フロイド・ワーシャル)のアルゴリズムを解説する。より計算量の小さいアルゴリズムも存在する(例えば、負辺が存在しないときは辺の数を \(m\) としてダイクストラ法 \(n\) 回で \(O(nm+n^2\log(n))\))ものの、Floyd-Warshall 法はその実装のシンプルさから多くの場面では有効なアルゴリズムである。

アルゴリズムの解説

頂点集合を \(V(G):=\{1,\ldots,n\}\) 、各辺 \(ij \in E(G)\) の長さを \(c_{i,j}\) と定義する。経由する内部頂点を \(\{1,2,\ldots,k\}\) に限定したときの \(i,j\) 間の最短道の長さを \(d_k(i,j)\) とすると求めたいのは \(d_n\) である。\(G\) に負閉路が存在しないとすれば、初期値は $$d_0(i,j) =\begin{eqnarray} \begin{cases}c_{i,j} & (ij\in E(G)) \\0 & ( i=j ) \\ \infty & ( \text{otherwise}) \\ \end{cases} \end{eqnarray}$$
となり、漸化式は
$$d_{k}(i,j)=\min(d_{k-1}(i,j),d_{k-1}(i,k)+d_{k-1}(k,j))$$である。負閉路が存在すると漸化式で計算している対象が道ではなくなってしまい正しい結果が得られない。漸化式から、次のコード(Python)にて \(d[i][j]\) が\(d_0(i,j)\) で初期化されていれば、ループ内で \(d[i][j] \leftarrow d_k(i,j)\) となる。

for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if d[i][k] < INF and d[k][j] < INF:
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

3重ループの結果として得られる行列 \(d\) が求めたい最短距離である。計算量は \(O(n^3)\)。

負閉路の検出

Floyd-Warshall のアルゴリズムにより負閉路の検出ができる。というのも、負閉路が存在するときに限り3重ループ後の \(d\) に \(d[i][i] < 0\) なる頂点 \(i\) が存在するからである。

負閉路が存在する場合、\(d\) の値の絶対値が一番外側のループ回数 \(k\) に対して指数関数的に増加する場合があるので、注意が必要である [1]。例えば、\(k\) 回目のループで、全ての \(i,j\) について \(d[i][j] < -2^k\) ならば \(k+1\) 回目のループでは \(d[i][j] <-2^{k+1}\) が成り立つので絶対値は \(\Omega(2^k)\) で増加する。漸化式を in-place で更新していることから、実際にはもっと速く \(\Omega(6^k)\) で増加するような簡単な場合が存在する[1]。オーバーフローを防ぐには、\(d[i][i] < 0\) を満たす \(i\) が存在しないか下記コードのように \(d\) の更新の度に確認すればよい。

for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if d[i][k] < INF and d[k][j] < INF:
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
            if i==j and d[i][j] < 0:
                print("negative cycle is detected")

更新順序の変更

足し算を min、掛け算を + に置き換えた行列積を考える(トロピカル半環)。行列 \(D^{(m)}\) の第 (i, j) 成分を頂点 \(i\) から 頂点 \(j\) に \(m\) 辺以下で到達する場合の最短距離と定義すると、\(D^{(i+j)}=D^{(i)}D^{(j)}\) が成り立つ。負閉路が存在しない場合、最短路は高々 \(n-1\) 辺で構成されるから、\((D^{(1)})^{2^{\lceil\log_2{n}\rceil}}\) によって答えが \(O(n^3\log{n})\) で求まる。これは、Warshall-Floyd のアルゴリズムのループ順を k-i-j から i-j-k にして、更新を in-place にしない場合に対応している。行列積の種々の高速化アルゴリズムは加法的逆元(minの逆操作)が存在しないので適用できない。しかしながら、[3] によると更新を in-place にし、k-i-j のループを “3” 回繰り返した次のコードでは正しい結果が得られる。

for _ in range(3):
    for i in range(1, n+1):
       for j in range(1, n+1):
          for k in range(1, n+1):
            if d[i][k] < INF and d[k][j] < INF:
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

参考文献

  1. Hougardy, Stefan. “The Floyd–Warshall algorithm on graphs with negative cycles.” Information Processing Letters 110.8-9 (2010): 279-281.
  2. Design and Analysis of Algorithms Lecture 11(Erik Demaine)
  3. ループの添字順序を間違えた Floyd-Warshall アルゴリズムを3回繰り返すと正しい結果が得られる

Published in アルゴリズム

Comments

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA