ワーシャルフロイド法

キーワード

• ワーシャルフロイド法
• 最短経路問題

概要

重み付きグラフの全ての頂点対間の最短経路を求めるアルゴリズム。 ダイクストラ法と異なり、負の辺があっても動作する。ただし、負の閉路がある場合は正しく動作しない。

最終的に $A_{ij}$ が頂点 $i$ から頂点 $j$ への最短経路の重みを表すような $n \times n$ 行列を得る。

まず次のように $A$ を初期化する。

次に、以下のように $A$ を更新する。

正当性

$k$ 回目の反復後の $A_{ij}$ を $d_{ij}^{(k)}$ とする。頂点 $1,2,\dots,k$ を中間点として使って良いとした時の $i$ から $j$ への最短経路の重みを$f_{ij}^{(k)}$ とする。 このとき、$f_{ij}^{(k)} = d_{ij}^{(k)}$ を $k$ について帰納的に示す。

$k=0$ のときは初期値なので明らかに成り立つ。

$k \geq 1$ に対して、$k-1$ 以下では成り立つと仮定する。

アルゴリズムの構成法から、$f_{ij}^{(k)} \leq d_{ij}^{(k)}$ が成立。($d_{ij}^{(k)}$ は頂点 $1,2,\dots,k$ を中間点として使って良いとした時の $i$ から $j$ へのある路の長さ)

従って、 $f_{ij}^{(k)} \geq d_{ij}^{(k)}$ が成り立つことを示せば良い。

頂点 $1,2,\dots,k$ を中間点として使って良いとした時の $i$ から $j$ への最短路を $P$ と置く。( $d(P) = f_{ij}^{(k)}$ )

$P$ が $k$ を通らないとすると、 $f_{ij}^{(k)} = f_{ij}^{(k-1)}$ である。帰納法の仮定より、 $f_{ij}^{(k-1)} = d_{ij}^{(k-1)}$ であり、アルゴリズムの構成法より、 $d_{ij}^{(k-1)} \geq d_{ij}^{(k)}$ である。従って、 $f_{ij}^{(k)} \geq d_{ij}^{(k)}$ である。

次に、 $P$ が $k$ を通る場合を考える。

このとき、 $P = (i, \dots, k, \dots, j)$ と書かれる。 $i,k,j$ 以外の点は $1,2,\dots,k-1$ のいずれかである。(負閉路を含まないため、同じ点が複数現れることはない)

よって、 $f_{ik}^{(k-1)} = d_{ik}^{(k-1)} = d(P_{i \to k}), \quad f_{kj}^{(k-1)} = d_{kj}^{(k-1)} = d(P_{j \to k})$ が成り立つ。ここで、 $P_{i \to k}$ は $P$ の $i$ から $k$ の部分路、 $P_{k \to j}$ は $P$ の $k$ から $j$ の部分路である。

従って、 $d_{ij}^{(k)} \leq d_{ik}^{(k-1)} + d_{kj}^{(k-1)} = d(P) = f_{ij}^{(k)}$ が言える。

以上より、 $f_{ij}^{(k)} = d_{ij}^{(k)}$ が成り立つ。

計算量

グラフの頂点数を $N$ とすると、 $\mathrm{O}(N^3)$

応用例

実装

func main() {
	var n, m int
	scanIntVariables(&n, &m)
	A := make([][]int, n+1)
	for i := 1; i <= n; i++ {
		A[i] = make([]int, n+1)
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= n; j++ {
			if i == j {
				continue
			}
			A[i][j] = 1 << 60
		}
	}
	for i := 0; i < m; i++ {
		var a, b, c int
		scanIntVariables(&a, &b, &c)
		A[a][b] = c
	}
	for k := 1; k <= n; k++ {
		for i := 1; i <= n; i++ {
			for j := 1; j <= n; j++ {
				A[i][j] = min(A[i][j], A[i][k]+A[k][j])
			}
		}
	}
}