概要

• 全点対間最短路問題が解ける（任意の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 代数の意味でのもの)

辺の追加