Transitive Closure
어떤 그래프 G가 있을 때, reachable한 vertex 사이에 직접적인 edge를 추가해 준 그래프를 말한다.
예를 들어 그래프 G에 A->B->C path가 존재하면, A는 C까지 reachable하므로 G의 transitive closure G*에는 A->C edge가 추가된다.
따라서 G*는 G의 superset이다.
Computing the Transitive Closure
어떤 그래프의 transitive closure를 구하기 위해서는 모든 vertex에 대해 서로 reachable한지 판단해야 한다. 그 방법은 무엇이 있을까?
DFS
첫 번째 방법은 모든 vertex에 대해 DFS를 수행해보는 것이다.
그래프를 adjacency list로 구현한 경우, DFS의 시간 복잡도는 O(n+m)이기 때문에, 모든 vertex에 대해 DFS를 수행하는 시간은 O(n(n+m))이 걸린다.
Floyd-Warshall
두 번째 방법은 Floyd-Warshall 알고리즘을 이용하는 것이다. 수도코드는 다음과 같다.
여기서 그래프 G는 adjacency matrix로 표현한다.
Gk는 k번째 vertex까지 이용하여 최단 경로를 구했을 때의 인접 행렬 상황을 나타낸다.
예를 들어, 1->k의 edge가 존재하고, k->5의 edge가 존재한다고 하자. 그러면 k를 이용하여 1->5까지의 path가 존재한다는 것을 확인하고, 1->5의 direct edge를 추가할 수 있다.
따라서, Gk-1에 1->5의 edge가 존재하지 않고, 1->k와 k->5 edge가 존재하면 Gk에 1->5 edge를 추가해주면 된다.
위의 과정을 모든 vertex에 대해 거쳐주면 transitive closure를 나타내는 G*를 얻을 수 있다. 이는 O(n3)의 시간이 소요되지만, 각 연산이 비교적 단순하다는 장점이 있다.
Floyd-Warshall로 All-Pairs-Shortest-Path 구하기
Floyd Warshall과 DP를 이용하여 모든 vertex 사이의 Shortest Path를 구할 수 있다. 수도코드는 다음과 같다.
i->j의 최단 경로를 구하는 점화식은 다음과 같다.
Dk[i,j] = min{Dk-1[i,j], Dk-1[i,k] + Dk-1[k,j]}
