• 概要
    • 全点対間最短路問題が解ける（任意の2点間の最短経路長が求まる）
    • 計算量: $O(n^3)$
  • ソースコード
  • ワーシャルフロイド法による負閉路検出
    • ワーシャルフロイド法をした後の距離行列を dist としたとき 「負閉路が存在 ⟺ ある i で dist[i][i] が負」
    • ただし、負閉路がある場合は dist の各値の絶対値は指数関数的に増加していくのでオーバーフローに注意。具体的には、dist の更新の都度 dist[i]i] が負になっているかどうかを確認すれば良い。
    • 参考
      • ワーシャル・フロイド法での全点対最短経路を求めるアルゴリズム | アルゴリズムロジック
      • ワーシャル・フロイドのアルゴリズム – 37zigenのHP
  • 経路復元
    • 参考: ワーシャル・フロイド法での全点対最短経路を求めるアルゴリズム | アルゴリズムロジック
  • 行列絡みの話

    • 行列累乗でも全点対間最短路長が求まる

      • 頂点数が $n$ のとき、隣接行列を $n$ 乗することで、全点対間最短路長が求まる。計算量は繰り返し二乗法を使うことで $O(n^3 \log(n))$
        • 行列の掛け算は min-plus 代数の意味の掛け算
      • 行列累乗しなくても $O(n^3)$ で求められるのがワーシャルフロイド法のすごいところ

    • ワーシャルフロイド法と行列の掛け算の計算は似ているけど、以下の違いがある

      • forループの回し方が違う（ワーシャルフロイド方がkij, 行列の積がijk）
      • 行列の積は新しく行列を作るけど、ワーシャルフロイド法だと既存の行列が逐次更新される（途中で更新した値が更新に使われる）

      [参考]

      • ワーシャルフロイド法と行列の掛け算のソースコード

    • ワーシャルフロイド法は隣接行列を2乗しているように見えるが違う。隣接行列の2乗をすると2手(以内)で移動したときの最短経路長が求まる。(ここで2乗は min-plus 代数の意味でのもの)