Do we need to know Warshalls Algorithm?
Good question! The answer is, yes, you do need to know Warshall’s Algorithm. Under certain circumstances, if you ever need to write a program that calculates reachability matrices, or transitive closure, you will need to be able to understand and use this algorithm. The alternative in most cases would be to write an overly slow, inefficient program. Warshall’s is a lot less work, Θ(n^3), compared to the Θ(n^4) required by the method of using powers of the adjacency matrix. This will not make a lot of difference for small n, but can make huge differences as n increases. It is true that Warshall’s is not necessarily understandable via a quick skim. However, few algorithms in discrete math are quite that easy. Usually careful reading and pondering are required, plus the working of many problems, and occasionally getting the help of someone else. Do not expect to understand most algorithms without spending time and thought. In addition, Warshall’s is not a particularly complicated algorith
