# Transitive Closure > [!summary] Definition Define the _transitive closure_ of $G$ as the graph > $G^* = (V, E^*)$, where > $E^* = \left\{(i, j) : \exists i \overset p\leadsto\ j\right\}$ - A solution: assign $w = 1$ to each edge and run [[floyd-warshall|Floyd-Warshall algorithm]]. - Substitute $\lor$ and $\land$ for $\min$ and $+$ operations in Floyd-Warshall algorithm. - $\Theta(n^3)$, space efficient