ワーシャルフロイド法

Floyd–Warshall Algorithm

日本語と英語でフロイドとワーシャルの順が逆なの謎

概要

グラフ上の全ての点の組について、最短距離を求める。

計算量

$ \Omicron (\left| V \right|^3)

実装

code:Warshal.py

V = 10 # 頂点数

# 辺の情報 dij := i -> j の辺のコスト到達不能はINF、dii = 0

d = [INF*V for _ in range(V)]

# ワーシャルフロイド法の核

for k in range(V):

for i in range(V):

for j in range(V):

dij = min(dij, dik + dkj)

仕組み

$ d[k][i][j] \coloneqq $ i から$ j まで、$ k 以下の頂点のみを通って行く最短距離とすると、

$ d[k+1][i][j] は、

$ k+1 を経由する$ i \rightarrow \dots \rightarrow k+1 \rightarrow \dots \rightarrow j というルートか、

$ k+1 を経由しない$ i \rightarrow \dots \rightarrow j というルートになる。

（共に$ \dots 部分は$ k 以下の頂点のみ）

$ k+1 を経由する最短距離は、

$ i \rightarrow \dots \rightarrow k+1 の部分が$ d[k][i][k+1] 、

$ k+1 \rightarrow \dots \rightarrow j の部分が$ d[k][k+1][j] となるので、

$ d[k][i][k+1] + d[k][k+1][j] 。

$ k+1 を経由しない最短距離は

単に$ d[k][i][j]

$ \therefore d[k+1][i][j]=\min(d[k][i][j], d[k][i][k+1] + d[k][k+1][j])

このdpをテーブル使いまわしで書いたものが上記のコードになる。

補足

負のコストがあっても正常に機能する。

$ \exist i \quad d[i][i] \lt 0 のとき、$ i のあたりに負のループが存在する。

例題