フロイド–ワーシャル法とは？仕組み・コード・計算量をわかりやすく解説

フロイド–ワーシャル法が解く問題

1つの始点からだけでなく、すべての場所の組の間の距離が必要になることがあります。全都市間の移動時間の表、全サーバー間のレイテンシ、依存関係グラフの完全な到達可能性などです。フロイド–ワーシャル法は、この全点対最短経路問題を、非常に短い動的計画法のアルゴリズムで解きます。

ロバート・フロイド（Robert Floyd）が1962年に発表し（"Algorithm 97: Shortest path"）、同じ1962年にスティーブン・ワーシャル（Stephen Warshall）が発表した推移的閉包のアルゴリズムを土台にしています。

考え方を言葉で説明すると

ノードに 0 から V − 1 まで番号を付けます。ノード k まで処理した後の dist[i][j] は、中継点としてノード 0 から k だけを使う場合の i から j への最短経路です。中継点にノード k を加えると、選択肢は2つです。k を避けた従来の最良経路か、k より前のノードだけを使う2つの最良経路をつないだ i → k → j です。

1. 行列を初期化します。対角成分は 0、辺がある箇所はその重み、それ以外は無限大です。
2. k = 0 から V − 1 まで、すべての組 (i, j) について、dist[i][k] + dist[k][j] < dist[i][j] なら更新します。
3. 最後の k の後に、行列にはすべての最短距離が入っています。対角成分に負の値があれば、負閉路があります。

ループの順序は本質的です。k が最も外側のループでなければなりません。

具体例で一歩ずつ確認

4つのノードと、辺 0→1（3）、0→3（7）、1→0（8）、1→2（2）、2→0（5）、2→3（1）、3→0（2）を持つ有向グラフです。初期の行列は次のとおりです（行 = 始点、列 = 終点）。

1. k = 0：経路はノード 0 を通れます。1→3 は 8 + 7 = 15、2→1 は 5 + 3 = 8、3→1 は 2 + 3 = 5 になります。
2. k = 1：ノード 1 を経由します。0→2 は 3 + 2 = 5、3→2 は 5 + 2 = 7 になります。
3. k = 2：ノード 2 を経由します。0→3 は 7 から 5 + 1 = 6 に、1→3 は 15 から 2 + 1 = 3 に、1→0 は 8 から 2 + 5 = 7 に改善されます。
4. k = 3：ノード 3 を経由します。1→0 は 7 から 3 + 2 = 5 に、2→0 は 5 から 1 + 2 = 3 に、2→1 は 8 から 1 + 5 = 6 に改善されます。

最終的な行列の各行は、0 → [0, 3, 5, 6]、1 → [5, 0, 2, 3]、2 → [3, 6, 0, 1]、3 → [2, 5, 7, 0] です。

Pythonでの実装

INF = float("inf")
def floyd_warshall(n, edges):
    dist = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    nxt = [[j if i == j else None for j in range(n)] for i in range(n)]
    for u, v, w in edges:
        dist[u][v] = w
        nxt[u][v] = v
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    nxt[i][j] = nxt[i][k]
    return dist, nxt
edges = [(0, 1, 3), (0, 3, 7), (1, 0, 8), (1, 2, 2),
         (2, 0, 5), (2, 3, 1), (3, 0, 2)]
dist, nxt = floyd_warshall(4, edges)
for row in dist:
    print(row)
# [0, 3, 5, 6]
# [5, 0, 2, 3]
# [3, 6, 0, 1]
# [2, 5, 7, 0]

nxt 行列には、i から j への最良経路の最初の一歩を保存します。これだけで任意の経路を復元できます。

def path(nxt, i, j):
    if nxt[i][j] is None:
        return []                         # no path
    route = [i]
    while i != j:
        i = nxt[i][j]
        route.append(i)
    return route
print(path(nxt, 1, 0))  # [1, 2, 3, 0]

ノード数が多くてPythonで速度が必要な場合は、同じ3重ループを、k ごとに1回のベクトル化された更新としてNumPyで書けます：d = np.minimum(d, d[:, k, None] + d[None, k, :])。

時間計算量と空間計算量

重みが非負の疎なグラフでは、全ノードからダイクストラ法を実行するコストは O(V × (V + E) log V) で、E が V² よりずっと小さければ O(V³) より高速です。

バリエーションとよくある間違い

• 負閉路：ループの後に、あるノード i で dist[i][i] < 0 なら、ノード i は負閉路上にあり、それを通る最短経路は定義できません。
• 推移的閉包（ワーシャル法）：真偽値を使い、min と加算を or と and に置き換えます：reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])。
• ミニマックス経路とマクシミン経路：+ を max（または min）に置き換えると、たとえば最大の辺が最も小さくなる経路が求まります。
• 無限大の代わりに大きな有限値を使うのは、2つを足してもオーバーフローしないと確信できる場合に限ってください。Pythonでは float("inf") が安全な選択です。
• 対角成分は 0 で初期化し、多重辺がある場合は最小の重みを残します。

使う場面と実世界での用途

• あとで参照するために、全駅・全倉庫・全都市の間の距離表を事前計算する。
• 小さなネットワークの近接中心性や直径など、グラフ分析。
• コーディング面接の問題：距離のしきい値以内にある隣接都市の数が最小の都市を探す、割り算の評価（比率を経路上の積とみなす）、推移的閉包としての履修前提条件。