Chap09. Transitive Closure, All-Pairs Shortest Paths

single-pair shortest path: Dijkstra's Algorithm
Floyd-Warshall's Algorithm

Transitive Closure

G*
the transitive closure of a digraph G
Gの頂点と同じ
u->v方向パスがある場合にエッジ情報が追加されます

edgeが存在する場合(G*の転送閉パケットを計算する)、図への到達性情報を迅速に提供することができる

Computing the Transitive Closure

n個のDFSを用いて、伝達閉パケットを求めることができる.O(n(n+m)) time
m密時(O(n 2 n^2 n 2)O(n 3 n^3 n 3にバインド)時間
idea
A->B、B->Cの場合、A->Cを選択できます

Floyd-Warshall Transitive Closure

はすべてのvertice番号です.|v|=n

1,2,...,

、すべての頂点からkへのパスを考慮

Floyed-Warshall's Algorithm

Algorithm FloydWarshall(G)
	Input digraph G
	Output transitive closure G* of G
	i <- 1
	for all v ∈ G.vertices()
		denote v as vi
		i <- i + 1
	G0 <- G
	for k <- 1 to n do
		Gk <- G{k-1}
		for i <- 1 to n (i != k) do
			for j <- 1 to n (j != i, k) do
				if G{k-1}.areAdjacent(vi, vk) ^ 
                		Gk - 1.areAdjacent(vk, vj)
					if ! Gk.areAdjacent(vi, vj)
						Gk.insertDirectedEdge(vi, vj , k)
		return Gn

input:graph G、各頂点番号
Input graph GをG 0にコピー
頂点ごとに移動可能な有向エッジ(G 1,G 2,...,Gk,...,Gn)を追加
G{k−1}を用いてGk−DPを計算する
are adjacentがO(1)に使用可能である場合、アルゴリズム実行時間はO(n 3 n^3 n 3)である.
−隣接行列法は、2つの頂点間の隣接情報を一定時間計算することを可能にする.

Floyed-Warshall Example

All-Pairs Shortest Paths

Algorithm AllPair(G) {assumes vertices 1,…,n}
for all vertex pairs (i,j) 
	if i = j
		D0[i,i] <- 0
	else if (i,j) is an edge in G
		D0[i,j] <- weight of edge (i,j)
	else
		D0[i,j] <- + infinite
for k <- 1 to n do 			// O(n) time
	for i <- 1 to n do 		// O(n) time
		for j <- 1 to n do 	// O(n) time
			Dk[i,j] <- min{Dk-1[i,j], Dk-1[i,k]+Dk-1[k,j]}
return Dn

input:有向図Gを重み付けし、すべての頂点ペアの最短距離を計算する
n次Dijkstra'sアルゴリズムは問題を解決できる
-負以外のエッジとしてのみ構成され、この場合heapを使用してO(nmnmnmlogn)timeを実行する
-稠密時のO(n 3 n^3 n 3 logn)時間
Floyed-Warshall'sアルゴリズムを使用した場合のO(n 3 n^3 n 3)時間
Example


最後までやりぬく
O(n),各行および各列O(n),従ってO(n 3 n^3 n 3)時間