C/C++ Program to find the Transitive Closure of a Relation

Warshall's Algorithm

  To find the Transitive Closure of a Relation an algorithm called Warshall's Algorithm is used. The transitive closure of a Binary Relation R on a Set X is the transitive relation R⁺ on the set X such that R⁺ contains R and R⁺ is minimal. The transitive closure can answer reachability question in case of graphs. Warshall's algorithm is also the back bone of Floyd-Warshall algorithm used to solve the All-Pairs Shortest Path problem in graphs. The Time Complexity of Warshall's Algorithm is O(n³) for a Relation involving n elements.

Click here to download the C Program implementing Warshall's Algorithm. 

Click here to download the C++ Program implementing Warshall's Algorithm.