【Python】ワーシャルフロイド法

ワーシャルフロイド法とは

任意の2頂点間の最短距離を求める問題を解くアルゴリズム

特徴

• 有効グラフでも無向グラフでも使える
• 辺に負の重みがあっても使える

計算量

O(|V|^3)

実装

# cost[i][j]: 頂点v_iから頂点v_jへ到達するための辺コストの和
# 頂点v_iから頂点v_jへの辺がない場合はINFを設定

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])