Floyd-Warshall アルゴリズム は重み付き有向グラフのすべての頂点対に対して最短路距離を求める代表的なアルゴリズムです．グラフの頂点を V={1,...,n}$V=\{1,...,n\}$ とし，n×n$n\times n$ 配列 d$d$ の (i,j)$(i,j)$ 成分をグラフの i,j$i,j$ 間の枝長 (枝がなければ ∞$\mathrm{\infty }$，i=j$i=j$ はゼロ) で初期化してから以下の３重ループを実行すると，すべての頂点 i$i$, j$j$ についてそれらの間の最短路長が d[i,j]$d[i,j]$ に入ります（ただしグラフは負閉路をもたないとします）．

# Floyd-Warshall アルゴリズム
for k = 1, ..., n:
  for i = 1, ..., n:
    for j = 1, ..., n:
      d[i,j] = min(d[i,j], d[i,k] + d[k,j])

ところで，Floyd--Warshall アルゴリズムのよくある実装ミスに「ループの添字の順序を間違える」ことがあります ¹ ．正しい順序 KIJ に対して，順序を間違えた実装をそれぞれ「IJK アルゴリズム」，「IKJ アルゴリズム」と呼ぶことにします．

# IJK アルゴリズム
for i = 1, ..., n:
  for j = 1, ..., n:
    for k = 1, ..., n:
      d[i,j] = min(d[i,j], d[i,k] + d[k,j])

# IKJ アルゴリズム
for i = 1, ..., n:
  for k = 1, ..., n:
    for j = 1, ..., n:
      d[i,j] = min(d[i,j], d[i,k] + d[k,j])

これらはもちろん正しい結果を出さないのですが，実は以下のことが証明できます．

定理 1. IJK アルゴリズムを３回実行すると d$d$ に正しい値が代入される．
定理 2. IKJ アルゴリズムを２回実行すると d$d$ に正しい値が代入される．

間違ったアルゴリズムを３回実行しても計算量は正しい Floyd-Warshall アルゴリズムとたかだか定数倍しか変わらないので，これらの結果から「Floyd-Warshall のループの添字順序がわからなくなったら，念のため３回実行すれば OK」ということがわかります．

証明のアイデア

３回・２回で十分であることを示すのは少し大変なので，ここでは基本的なアイデアをつかむために O(logn)$O(\log n)$ 回繰り返せば全点対間最短路長が正しく求まることを示します．

Floyd-Warshall アルゴリズムの更新 d[i,j] <- min(d[i,j], d[i,k] + d[k,j]) は，グラフの頂点対 i,j$i,j$ に新しい枝を張る（長さは k$k$ を中継したときの距離）操作に対応します．ここで重要となるのは この更新によってグラフの最短路長は変化しない（ただし最短路そのものは変化しうる） という性質です．定理の証明では，適当な回数アルゴリズムを繰り返すことでグラフが長さ１の最短路をもつようになることを示します．

定理 3. IJK アルゴリズムもしくは IKJ アルゴリズムを O(logn)$O(\log n)$ 回実行すると d$d$ に正しい値が代入される．

証明．
適当に頂点 s,t∈V$s,t\in V$ を固定し，それらの間の最短路 [u0,u1,…,ul]$[u_0,u_1,\dots ,u_l]$ をとる (s=u0,t=ul$s=u_0,t=u_l$)．すると，IJK アルゴリズムもしくは IKJ アルゴリズムを実行することでグラフに新たに枝 (u0,u2),(u2,u4),…$(u_0,u_2),(u_2,u_4),\dots$ が追加されるので，アルゴリズム実行後のグラフは長さが元の半分の s,t$s,t$ 間最短路 [u0,u2,…,ul]$[u_0,u_2,\dots ,u_l]$ をもつ．したがってアルゴリズムを O(logn)$O(\log n)$ 回繰り返すとグラフは長さ 1$1$ の最短路をもつようになる．これは d$d$ が全点対間最短路長であることを意味する．//

反復回数が３回・２回で十分なことを示すには，アルゴリズム実行後に「特殊な添字構造をもつ最短路」がとれることを示すことになります．詳しくは https://arxiv.org/abs/1904.01210 を参照してください．

経緯