각 vertex가 source일 때의 paths를 모두 구하는 알고리즘을 알아보자

Using SSSP algorithms

Single source shortest paths 에서 배운 알고리즘을 이용할 수 있다.

하나의 Single source shortest paths 알고리즘을 각 vertex가 source인 경우로 $|V|$ 번 실행하면 된다.

Nonnegative-weight edges

• Dijkstra's algorithm

  • Using unsorted array: $O(V\cdot V^2)$

  • Using Min-heap: $O(V\cdot (VlogV + ElogV))$ = $O(V^2logV + VElogV)$

    • $E = \theta(V)$ 라면 $O(VElogV)$으로, Floyd-Warshall algorithm보다 빠르다.

Negative-weight edges

• Bellman-Ford algorithm
  • $O(V \cdot VE) = O(V^2E)$
  • 만약 Dense graph ($E = O(V^2)$)라면, $O(V^4)$ 이다.

Floyd-Warshall algorithm

Dynamic programming을 이용하여 All-pairs shortest paths 를 구하는 알고리즘

• Optimal substructure이다.

필요한 것

1. Adjacency Matrix W

   • Edge $(i, j)$의 weight를 저장: $w_{ij} = w(i, j)$
   • Edge가 존재하지 않는다면 $\infty$
     

2. Shortest Distance Matrix D

   • Vertex $i$ 부터 $j$ 까지의 Shortest Distance를 저장: $δ(i,j)$
   • Self loop가 존재하지 않기 때문에 Diagonal element = 0
     

3. Predecessor Matrix $\Pi$

   • $\pi_{ij}$: $i$ 부터 $j$의 path가 존재할 때, Vertex $j$의 Predecessor vertex
   • $\pi_{ij} = NIL$: $i$ 부터 $j$의 path가 존재하지 않거나, $i = j$
     

4. Intermediate Vertex

   • Path p = <$v_1, v_2, ... , v_l$> 이 있을 때, $v_1$ 과 $v_l$ 사이에 존재하는 vertex
   • K가 Intermediate vertex of path $(i,j)$ 라고 하면 해당 Path에는 Vertex k가 반드시 포함되어야한다.

초기 세팅

• Distance matrix를 Adjacency matrix로 초기화한다.
• $D^{(0)} = W$
  

가정

K: Intermediate vertex 라고 하면 Path $(i, j)$ 에는 다음 두 가지 가정이 존재한다.

1. K가 Path $(i, j)$의 Intermidate vertex인 경우

   • 이 경우, Path $(i, j)$를 Path $(i, k)$ 와 Path $(k, j)$ 로 나눌 수 있다.
   • $d_{ij} = d_{ik} + d_{kj}$

2. K가 Path $(i, j)$의 Intermidate vertex가 아닌 경우

   • 이 경우, 단순히 Path $(i, j)$를 계산하면 된다.

과정

1. K = 1 to N까지 각 K에 대해$d_{ij}^{(k)} = min(d_{ij}^{(k-1)} , d_{ik}^{(k-1)} + d_{kj}^{(k-1)})$ 을 수행한다.

2. (1) 의 결과를 $D^{(k)}$에 저장한다.

3. K = N 이라면 알고리즘을 종료한다.

Pseudo code

FLOYD-WARSHALL(W) 
1.  n = W.rows
2.  D^0 = W
3.  for k = 1 to n
4.  	let D(k) = (d_ij(k)) be a new n x n matrix
5. 		for i = 1 to n
6.			for j = 1 to n
7. 				d_ik(k) = min(d_ij(k-1), d_ik(k-1) + d_kj(k-1))
8.  return D(n)

PRINT-ALL-PAIRS-SHORTEST-PATH(Π, i, j)
1.  if i == j
2.		print i
3.  else if π_ij == NIL
4.		print "no path form" i "to" j "exists"
5.  else PRINT-ALL-PAIRS-SHORTEST-PATH(Π, i, π_ij)
6.		print j

Running time

• Line 7: $O(1)$
• Total Running time: $\theta(V^3)$
  • Line 7이 $n^3$번 호출되기 때문이다.

Predecessor matrix로 Shortest path 계산

• (k)의 의미는 k를 거쳐갔을 때를 가정한다는 의미이고 $\Pi$는 $j$의 직전 vertex를 의미한다.

Transitive closure of Graph

Directed graph $G = (V, E)$ 에 대해 Transitive closure of $G^* = (V, E^*)$

• $E^*$: Path $(i, j)$ 를 구성하는 Egde의 집합