Transitive Closure, All-pairs Shortest Paths

- single pair shortest는 다익스트라, all-pairs shortest는 Floyd-Warshall

 

Transitive Closure

- digraph G의 transitive closure G’는

- G의 정점을 모두 가짐d

- G에 u->v인 경로가 있다면(직접연결이 아니어도), G’는 u->인 directed edge를 가짐

  (G에 a->b>c 경로가 있다면, G’에 a->c를 추가한다.)

- n번의 DFS로도 (O(n(n+m))->O(n3)) 가능하지만, 대신 dynamic programming:Floyd-Warshall !

 

Floyd-Warshall Algorithm으로 transitive closure 만들기

- n*n 배열을 만들고, 연결된 정점은 1로 채움

- 세로로 순서대로 읽으면서 1인 행에 방문해 그 행 중 1에 해당하는 vertex를 추가한다.

 

All-Pairs Shortest Paths 만들기

- 다익스트라를 n개의 정점에 대해 호출해 만들 수도 있지만, O(nmlogn)->O(n3logn) time 걸린다. (heap)

- 플로이드 워셜과 유사한 dynamic programming으로 O(n3) time에 얻을 수 있다.

- 각 Phase에서 O(n2)인 과정을 n번

- 위와 비슷한 방법인데 weight가 있음. 더 작은 것으로 계속 업데이트