ワーシャルフロイド法
中継点 k を 1 つずつ許可しながら、全点対最短経路 D[i][j] = min(D[i][j], D[i][k] + D[k][j]) を距離行列の上で追います。
5
なし
編集モードでは現在 k = なし にリセットして編集します。重みはランダム（1〜9）で付きます。
許可中の中継点 k
—
このステップの更新数
—
累計更新数
—
完了
—
グラフ（有向・辺の数字＝重み）
距離行列 D[i][j]（行 i → 列 j・∞ は到達不能）
ワーシャルフロイド法は、すべての頂点ペア (i, j) の最短経路を一度に求めるアルゴリズムです。
アイデアは「中継点 k を 0 個、1 個、2 個… と少しずつ許可していく」こと。中継点 k を新たに許可したとき、 i → k → j の経路が今の i → j より短ければ、距離を更新します（
すべての k を許可し終えると、D は真の全点対最短距離になります。k スライダーや「k を 1 つ進める」ボタンで、行列のどのセルが短縮されたかを 1 ステップずつ追ってみましょう。
アイデアは「中継点 k を 0 個、1 個、2 個… と少しずつ許可していく」こと。中継点 k を新たに許可したとき、 i → k → j の経路が今の i → j より短ければ、距離を更新します（
D[i][j] = min(D[i][j], D[i][k] + D[k][j])）。すべての k を許可し終えると、D は真の全点対最短距離になります。k スライダーや「k を 1 つ進める」ボタンで、行列のどのセルが短縮されたかを 1 ステップずつ追ってみましょう。
いま何が起きている？
ここがポイント
- 中継点を 1 つずつ許可 ── k 番目の頂点を経由してよいとき、各ペアを更新する。これを全 k で繰り返す。
- 更新条件は
D[i][k] + D[k][j] < D[i][j]── i→k と k→j を繋いだ方が短ければ短縮（行列で黄色く光るセル）。 - 3 重ループ O(N³) ── 外側が k、内側が i・j。k のループが一番外側なのがミソ。
- ∞ の扱い ── 到達不能は ∞。∞ を含む和は更新に使わないのでガードする（このページも発散しない）。