**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^{3})**n**elements.
## No comments:

## Post a Comment