From our answers to questions from readers...

[EagleRidge Home] | [Resources] |

Warshall's Algorithm Advice: Tips for Discrete Math and Computer Science Students

Do we need to know Warshall's Algorithm? It looks pretty complicated to me. I skimmed quickly through it and am not sure what it is and not really understanding it.

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 algorithm as algorithms go and it should be the goal of any professional programmer or developer to be ready to implement this or many other algorithms, should one be needed.

So, yes, you do need Warshall's algorithm. However, the important lesson here is not Warshall's alone, but that as a programmer and developer you may be called upon to understand and implement many algorithms like this or even more difficult ones in the course of your career. The best programmers are aware of as many algorithms for efficient handling of tasks as possible, so as to be able to implement the best algorithm available for the task at hand. Often your manager will expect you to figure out the algorithms to use on your own, as part of your craft rather than telling you the ones to use. Hence you cannot rely on your supervisors telling you what ones to use; the best solution for someone who wants to become a good programmer is to study algorithms and keep studying them as time passes (since better algorithms are sometimes developed).

There are whole sequences of classes and many books, just on algorithms, at both the undergraduate and graduate levels in computer science.

The best algorithm to use for calculating reachability will depend on the type of graph(s) being examined and on the exact information needed to be calculated. For a more detailed discussion of the algorithms that might be used in various circumstances for computing reachability and transitive closure, see Dr. Skiena's The Algorithm Design Manual: The CD-ROM.  Note that this book calls Warshall's simple and slick.

Again, just because there are more difficult, more complicated algorithms out there, and Warshall's is considered relatively simple do not set yourself up for disappointment by having unreasonable expectations. These algorithms, even the so-called simple ones, require thought and hard study, and skimming quickly over them will not be sufficient for understanding and mastery.

The good news is that most of us must go through that same thought and hard study, so you are not alone.

--Crystal Sloan
2003

Note: Big-Theta notation uses the Greek letter capital theta or just plain Theta, which looks like a standing oval with a belt across its middle: Θ. Big-Theta notation is similar to the big-O of Landau notation.

[Legal Stuff]
Used with permission of the author.