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와 vertices가 같음
u->v directed path가 존재할 때 directed edge 정보 추가

edge가 바로 존재하면(G*의 transitive closure을 계산하고 나면) digraph의 reachability information을 빠르게 제공 가능

Computing the Transitive Closure

n번의 DFS로 transitive closure을 구할 수 있음. O(n(n+m)) time
m이 dense할 경우(O($n^2$)에 bound) O($n^3$) time

idea
A->B, B->C가 있을 때, A->C 가능

Floyd-Warshall Transitive Closure

1. 모든 vertice에 대해 번호 부여. |v|=n
2. 1,2,...,k까지 모든 vertices들의 path를 고려함

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, 각 vertex에 번호를 매김
input graph G를 G0에 복사
각 vertex를 통해 갈 수 있는 directed edge를 추가해줌(G1,G2,...,Gk,...,Gn)
G{k-1}로부터 Gk 계산 - DP 활용
areAdjacent를 O(1)에 수행할 수 있을 때 알고리즘 수행 시간은 O($n^3$)
- 두 vertex 간에 adjacency 정보를 상수 시간에 계산할 수 있는 것은 adjacency matrix 방법

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: weighted directed graph G, 모든 정점 쌍에 대한 shortest distance 계산
n번의 Dijkstra's algorith 수행 시 문제 해결 가능
- 단, nonnegative edge로만 구성, 이 경우 heap을 이용하여 O($nm$log$n$) time
- dense할 경우 O($n^3$logn) time
Floyed-Warshall's Algorithm 이용 시 O($n^3$) time

Example


끝까지 진행

n phases이므로 O(n), 각 행과 열 O(n), 따라서 O($n^3$) time