Namaran

Code daily. Without assist.

2026-10-14

min_over_k.rs

const INF: u32 = u32::MAX;

fn main() {
    let mut d = [
        [0, 1, 5, INF, INF],
        [INF, 0, INF, 1, INF],
        [INF, INF, 0, INF, INF],
        [INF, INF, 1, 0, 1],
        [INF, INF, INF, INF, 0],
    ];
    for i in 0..5 {
        for j in 0..5 {
            d[i][j] = (0..5).map(|k| d[i][k].saturating_add(d[k][j])).min().unwrap();
        }
    }
    println!("{:?}", d[0]);
}

これは何を出力するでしょうか?

Answer

[0, 1, 5, 2, 3] です。

d は、5つの頂点(vertex)を結ぶ向き付きの辺(edge)の長さの表で、d[i][j] が頂点 i から j へ直接向かう辺の長さ、辺がなければ INF です。ループは各 d[i][j] を、k をすべて動かしたときの d[i][k] + d[k][j] の最小値で置き換えます。k = i なら d[i][i] が0なので、この最小値には今の d[i][j] 自身も入り、値が増えることはありません。最短経路(shortest path)の長さの定義そのものに見える式ですが、k のループがいちばん内側にあるので、各 (i, j) は1回ずつしか更新されません。

i = 0 の行は j の小さい順に更新され、求めた値はすぐ d に書き戻されます。j = 2 のとき、0→1→3→2 の長さ3を見つけるには d[0][3] が2になっている必要がありますが、d[0][3] を更新するのは j = 3 の番で、まだ INF です。ほかに使える経路は直接の辺の5しかないので、d[0][2] は5のまま残ります。

逆に、先に書き戻された値は後ろの j で使われます。j = 3 で d[0][1] + d[1][3] から2が入り、j = 4 ではその2に d[3][4] の1を足して3になります。辺を3本通る 0→1→3→4 が見つかるのはこのためです。結果は、本当の最短距離 [0, 1, 3, 2, 3] とも、辺2本までの経路だけを見たときの値(d[0][4] が INF のまま)とも違うものになります。

k のループを3重ループのいちばん外に出すと、d[0][2] も3になります。これがワーシャル・フロイド法(Floyd-Warshall algorithm)の形で、k 回目の繰り返しを終えた時点の d[i][j] は、途中で通る頂点を0から k までに限ったときの最短距離になります1。最後の k を終えれば、どの頂点を通ってもよい最短距離が求まります。

  1. k 回目では、途中で k を通らない経路の長さは前の回の d[i][j] に、k を通る経路の長さは前の回の d[i][k] + d[k][j] に入っています。この2つの小さいほうを取れば、通ってよい頂点が1つ増えた最短距離になります。