定義

フロイド-ワーシャルは「全ての点から全ての点への最短距離」を一度に求めるアルゴリズムです。経由点を一つずつ増やしながら、より短い経路があるか確認します。

主な特性

• ✓全点対最短経路：一回の実行で全ての(i, j)ペアの最短距離を計算します。
• ✓動的計画法：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])の漸化式を使用します。
• ✓負の重み対応：負のサイクルがなければ負の辺も処理可能です。

時間計算量