全点対最短経路(ワーシャルフロイド法)

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

概要

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

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

計算量

$O(|V|^3)$

実装

# N: 頂点数
# cost[i][j]: 頂点 v_i から頂点 v_j へ到達するための辺コストの和
N = ...
cost = [[...] for i in range(N)]

INF = 10**18
for k in range(N):
    for i in range(N):
        for j in range(N):
            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)

戻る