플로이드-와샬 알고리즘

1. Transitive Closure : Digraph G가 주어졌을때, u-v사이에 path가 존재하면 u-v사이의 directed edge를 추가한게 G*, transitive closure이다. EX) G에서 B->D->E 를 연결하는 path가 있으면 B->E directed edge를 추가한다. -> 이는 diagraph에서 reachability information을 제공할 수 있다. 2. Transitive Closure는 어떻게 알 수 있는가? 1) 모든 정점에 대해서 DFS를 수행한다. O(n(n+m)) -> 정점에서 reachable한 vertex를 찾는 DFS를 모든 정점에 대해서 수행해야 한다. : 만약 Graph가 Dense하다면 최악의 경우엔 O(n^3), Sparse하다면 ..