フロイド–ワーシャル法とは？全点対最短経路の基礎・実装・負の重みと負の閉路への対処

2025年11月20日 最終更新日時 : 2025年11月20日 エバープレイ編集部

概要 — フロイド–ワーシャル法とは

フロイド–ワーシャル法（Floyd–Warshall algorithm）は、重み付き有向グラフにおける全点対最短経路（All-Pairs Shortest Paths, APSP）を求める古典的なアルゴリズムです。すべての頂点対 (u, v) について、u から v への最短距離を行列形式で計算します。負の重みを持つ辺を扱えますが、負の閉路（サイクル）の存在下では最短経路が定義できないため注意が必要です。

歴史的背景

同様の考え方は複数の研究者により独立に示されました。代表として Robert W. Floyd（1962）と Stephen Warshall（1962）の名が一般に付されます（先行研究として Roy 等も知られています）。Warshall の研究はブール行列による可達性（推移閉包）に関するものであり、Floyd の記述は最短路問題への応用として体系化されました。

基本的な考え方（動的計画法）

フロイド–ワーシャル法は動的計画法に基づきます。頂点集合 V = {1, 2, ..., n} が与えられたとき、アルゴリズムは「使用可能な中継頂点の集合を {1..k} に制限したときの最短距離」を再帰的に構築します。すなわち、dist_k[i][j] を「中継に頂点 1..k のみを許す i→j の最短距離」と定義すると、遷移は次のようになります。

  • dist_0[i][j] は直接辺 (i, j) がある場合その重み、ない場合は +∞（ただし i = j のとき 0）
  • dist_k[i][j] = min(dist_{k-1}[i][j], dist_{k-1}[i][k] + dist_{k-1}[k][j])

これを k = 1..n の順で反復すれば、最終的に dist_n が全点対最短距離行列になります。

擬似コード

入力: 頂点数 n, 初期距離行列 dist（dist[i][j] = w(i,j) または +∞）
for k = 1 to n:
  for i = 1 to n:
    for j = 1 to n:
      if dist[i][j] > dist[i][k] + dist[k][j]:
        dist[i][j] = dist[i][k] + dist[k][j]
出力: dist（全点対最短距離行列）

経路復元を行いたい場合は、next[i][j]（または successor[i][j]）行列を用意します。初期化は、辺 (i,j) が存在するなら next[i][j] = j、存在しないなら next[i][j] = NULL とします。更新時に dist を更新したら next[i][j] = next[i][k] に設定します。任意の i→j の経路は next を辿ることで復元できます。

負の重みと負の閉路の検出

フロイド–ワーシャル法は負の重み（負の辺）を含むグラフでも正しく動作します（局所的に負の辺があっても問題ありません）。ただし、負の閉路（ある頂点 v について最短距離 dist[v][v] が負になる）は、最短路の概念を破壊します。アルゴリズム終了後に任意の v で dist[v][v] < 0 なら、グラフに負の閉路が存在すると判定できます。負の閉路がある場合、最短経路は定義できない（任意に短くできる）ため、応用側で特別な扱いが必要です。

経路復元の具体例（手順）

経路復元の一般的手順は次の通りです。

  • 初期化: next[i][j] = j（辺がある場合）、next[i][j] = NULL（辺がない場合）。next[i][i] = i にする実装もある。
  • 更新: dist[i][j] を dist[i][k] + dist[k][j] で更新したら next[i][j] = next[i][k] に置き換える。
  • 復元: start = u, end = v。もし next[u][v] が NULL なら経路なし。そうでなければ path = [u]。while u != v: u = next[u][v]; path.append(u)。

計算量と記憶量

  • 時間計算量: O(n^3)。三重ループ（k, i, j）によるため、頂点数 n が増えると立方時間になります。
  • 空間計算量: 通常は O(n^2)（距離行列と経路復元用 next 行列を保持する場合は 2×O(n^2)）。

したがって、密なグラフ（辺数が O(n^2) に近い）や n が中程度（数百程度）までの問題に適しています。巨大な稀なグラフでは、Johnson のアルゴリズムや各頂点から Dijkstra を個別に回す方法の方が有利になる場合があります。

正しさの直感的な証明（帰納法）

k を段階として扱い、帰納法で証明します。ベース k = 0 では dist_0 は直接辺だけを用いる最短距離で正しい。仮に dist_{k-1} が正しいとすると、dist_k は「中継に k を使わない場合」と「中継に k を使う場合（i→k、k→j の両方とも中継は 1..k-1 に限る）」の二択を取るので min によって最短を得ます。これを k = n まで進めれば全中継を許した最短距離が得られる、というのが本質です。

実装上の注意と最適化

  • 数値オーバーフロー: 距離を表す型に注意し、無限大を十分大きな値で表現するか、適切な浮動小数点／整数の扱いを行う。
  • キャッシュ効率: 単純三重ループでもループ順序（k,i,j や k,j,i など）やブロッキング（分割して計算）でキャッシュヒット率が変わり実行速度に差が出る。大規模な実装ではブロック化やSIMD、GPU を使った並列化が有効。
  • 分散・並列実行: k ループは逐次的だが、固定した k の内部（i, j の更新）は独立なので並列化できる。MPI や OpenMP・GPU 実装が現実的。
  • トランジティブクロージャ: 重みを無視した到達可能性（可達性行列）を求める Warshall のアルゴリズムは、フロイド–ワーシャルのブール代数版と見なせる。ビットセットを使うと高速化できる。

他アルゴリズムとの比較

  • Dijkstra: 単一始点最短路 (SSSP) に特化。非負重みなら Dijkstra を各頂点から実行（ヒープを使えば O(n * (m log n)) 等）する選択肢がある。稀なグラフ（辺数 m が小さい）では Dijkstra を繰り返す方が速い。
  • Johnson のアルゴリズム: グラフに負の重みがあっても Bellman–Ford で再重み付けしてから各頂点で Dijkstra を行う手法。スパースグラフで有用で、時間計算量は O(n m + n^2 log n)（実装のヒープ選択に依存）など。
  • フロイド–ワーシャル: 実装が非常に簡潔で、密グラフや n が小から中規模の場合に実用的。負の辺を直接扱える点が強み。

応用例

  • ネットワーク解析（全点対距離を事前に持ちたい場合）
  • トランジティブクロージャ（到達可能性）の計算（Warshall）
  • ルーティングテーブルの事前計算（小規模ネットワーク）
  • グラフの中心性指標（全頂点からの距離和など）の計算
  • 制約満足や論理推論での閉包計算（ブール代数バージョン）

実装例（簡易的なポイント）

実装は行列を用いるのが典型で、言語により 2 次元配列を用いて三重ループをそのまま書けば良いです。Python、C++、Java いずれでも簡潔に実装できます。経路復元が必要な場合は next 行列を併用してください。

まとめ

フロイド–ワーシャル法は、簡潔かつ一般性の高い全点対最短路アルゴリズムです。負の辺を扱える点や、行列操作によりトランジティブクロージャへも容易に応用できる点が魅力です。一方で O(n^3) の時間がかかるため、頂点数が非常に大きいグラフやスパースグラフでは Johnson や個別に Dijkstra を適用する手法の方が適している場合があります。実装時は負の閉路の検出、数値の取り扱い、キャッシュ効率や並列化などに配慮するとよいでしょう。

参考文献

カテゴリー
IT
前の記事
ベルマン–フォード法とは？負の重みと負の閉路検出を徹底解説する単一始点最短経路アルゴリズムの完全ガイドNew!!
2025年11月20日
次の記事
A*アルゴリズム完全ガイド：概要・歴史・原理・実装・応用New!!
2025年11月20日