Asymtotic run time needed to compute the transitive closure of a graph?

Question

The transitive closure of a graph is defined e. g. here: http://mathworld.wolfram.com/TransitiveClosure.html

It is easily possible in O(n^3), where n is the number of vertices. I was wondering if it can be done in time O(n^2).

Answer 1

Nope. I don't think there is a O(n²) algorithm for it. I would expect if such an algorithm existed, you could solve all pair shortest paths problem in O(n²) too, which is not the case. The asymptotically fastest algorithm I can think of is an implementation of Dijkstra's shortest path algorithm with a Fibonacci heap (O(n²log n) in not very dense graphs).