ワーシャルフロイド法 (Warshall-Floyd Algorithm)

概要

全点対最短経路問題(APSP)を解くアルゴリズム。

グラフ\(G = (V, E)\)の全てのペア\((v, w)\)間の最短経路コストを求める。

計算量

\(O(|V|^3)\)

実装

# cost[i][j]: 頂点v_iから頂点v_jへ到達するための辺コストの和
for k in range(V):
    for i in range(V):
        for j in range(V):
            if cost[i][k]!=INF and cost[k][j]!=INF:
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])

Verified

  • AOJ: "GRL_1_C: Shortest Path - All Pairs Shortest Path": source (Python2, 0.67sec)