Monday, 21 January 2013

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(n3) for a Relation involving n elements.