Transitive Closure

Definition Define the transitive closure of $G$ as the graph

$G^{\ast }=(V,E^{\ast })$, where $E^{\ast }=\left\{(i,j):\exists i\stackrel{p}{⇝}j\right\}$

• A solution: assign $w=1$ to each edge and run Floyd-Warshall algorithm.
• Substitute $\vee$ and $\wedge$ for $\min$ and $+$ operations in Floyd-Warshall algorithm.
• $\Theta (n^3)$, space efficient