ワーシャル・フロイドのアルゴリズム

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

アルゴリズムの解説

頂点集合を $V(G):=\{1,\ldots,n\}$ 、各辺 $(i,j) \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} & ((i,j)\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)$。

ループの順序を k, i, j から i, j, k にすると正しい値が求まらない。例えば、①→④→③→②というグラフで i, j, k の順に更新すると、① → ② の長さが初期値の $\infty$ から更新されない。

負閉路の検出

ワーシャル・フロイドのアルゴリズムにより負閉路の検出ができる。というのも、負閉路が存在するときに限り３重ループ後の $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})$ で求まる。これは、ワーシャル・フロイドのアルゴリズムのループ順を 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])