グラフ系アルゴリズム:ワーシャル・フロイド法

今回は競技プログラミングの記事です。

グラフの中の任意の2点間の最短距離を求められるアルゴリズム、ワーシャル・フロイド法(Floyd–Warshall Algorithm)のご紹介です。日本語と英語で逆なんですねー。

過去にご紹介したダイクストラ法やベルマン・フォード法は、ある始点を1点に定めてアルゴリズムを動かしましたが、ワーシャル・フロイド法は任意の2点間の最短距離を求めることができます。

また、ワーシャル・フロイド法もベルマン・フォード法と同じく、コストが負となる辺が含まれていてもよく、負閉路が存在するかどうかも検出することができます。

計算量はノードの数を  V として  O(V^{3}) です。ダイクストラ法やベルマン・フォード法を各点を始点として実行するよりかはおそらく早く動くはずです。

スクリプトはこちらのようになります。

import itertools

class WarshallFloyd:
    def __init__(self, costs):
        self.n = len(costs)
        self.costs = costs

    def solve(self):
        dp = [
            [0 if i == j else cost_i2j for j, cost_i2j in enumerate(cost_i2x)]
            for i, cost_i2x
            in enumerate(self.costs)
        ]
        for k, i, j in itertools.product(range(self.n), repeat=3):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
        return dp

使い方としてはこんな感じになります。

# graph は隣接行列で用意いただく想定です。
graph = [[[...]]]

d = WarshallFloyd(graph)
d.solve()
# => [[d00, d01, ... d0n-1], [d10, d11, ... d1n-1], ..., [dn-10, dn-11, ... dn-1n-1]]
# 各点から各点への最短距離がリストのリストで手に入ります。

負閉路が存在する場合、その閉路上に存在するノード  i について、dp[i][i] が負の値になります。負経路の検出はこの性質を用いて行ってください。