ワーシャル・フロイド法の解説

ワーシャル・フロイド法の主にループの順番にややこしさを感じたので, 整理もかねて, 本稿ではワーシャル・フロイド法について解説していきます.

ワーシャル・フロイド法とは

$n$頂点有向グラフ$G$の全頂点間の最短路の長さを調べるアルゴリズムです.
Pythonで書くと以下のようになります.

for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

解説

特徴的なのは変数の順番でしょう. 始点$i$, 終点$j$, 経由点$k$からなる三重ループとなっていて, $k$のループが一番最初に来ているのが特徴的です.
$k$が最後に変動するので, dist[i][j]には$\{ 1, 2, 3, ..., k-1 \}$の経由点のみを通過していい場合のときの$i$から$j$までの最短路の長さ, dist[i][k] + dist[j][k]は$i$から$k$を通り, $j$にまで行くときの最短路の長さとなっています. 後者においても経由点は$\{1, 2, 3, ..., k-1\}$までに限定されています.
よって, この両者のうち小さいほうであるminは$i$から$j$まで, $\{1, 2, 3, ..., k\}$の経由点のみを通過していい場合の最短路の長さとなります.

変数の順番を変えたとき

for i in range(n):
    for j in range(n):
        for k in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

こちらのほうが変数の順番が自然に見えます. しかし, これで実行しても正しい最短路の長さが求まりません.

理由

コードを以下のように書き直すとわかりやすいかもしれません.

for i in range(n):
    for j in range(n):
        dist[i][j] = min(dist[i][k] + dist[k][j] for k in range(n))

すなわち, $i$と$j$の間の最短路はすべての経由点について調べて, その最も短いものとなるものが最短路の長さとなると言っています.
正しく求められた$dist$の上では, 確かにこの主張は正しいといえます. しかし, 今回のコードでは, k > jとなるような$k$においてはまだ$dist[i][k]$が正しく求められていない状態にあります. もしこのような$k$が最短路に含まれる頂点の一つであったならば, 最短路は正しく求められないでしょう.
一方で, 正しいワーシャル・フロイド法のアルゴリズムについてみてみると, dist[i][k], dist[k][j]のどちらについても, 確かに$\{1, 2, 3, ..., k-1\}$のみしか経由点としていないことが保証されるので, こちらが正しく作用すると言えます.

経路復元

二重リストprevを用意し, $prev[from][to] = k$であるならば, $from \rightarrow ... \rightarrow k \rightarrow to$が最短路となるようにします. dist[i][j]を更新するタイミングでprevも更新します.

for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][k] + dist[k][j] < dist[i][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
                prev[i][j] = prev[k][j]

実際経路が必要となったときはこの二重リストを逆にたどれば求められるでしょう.

終わりに

大学のグループワークで使うことになったので, 誰かに聞かれても説明できるようにと思って書きました. 変数の順番とかすっきりしたのでよかったです.
最近はRustばっか書いてますが, こうしたときにPythonは疑似コードとしても使えるので重宝しています.