An answer to this question on Stack Overflow.

Question

for an assignment I am asked by to find find an algorithm that calculates the transitive closure of a directed graph using O(n 4 ) time. We already learned about the floyd warshall algorithm, which is a lot better, so can someone help me create one that runs in O(n4) time? is there such an algorithm?

I know it seems dumb of a question. I dont really understand why we are being asked to find the slower way to do it.

Answer

The Floyd-Warshall Algorithm for transitive closure looks like:

int dist[N][N];  // For some N
int i, j, k;
// Input data into dist, where dist[i][j] is the distance from i to j.
// If the nodes are unconnected, dist[i][j] should be infinity
for ( k = 0; k < N; k++ )
for ( i = 0; i < N; i++ )
for ( j = 0; j < N; j++ )
   if(dist[i][k] && dist[k][j])
      dist[i][j] = 1;

Note the order of the indices used: they are ordered this way to preserve an optimal substructure property. If we instead reorder them as below, that property is violated:

  for ( i = 0; i < N; i++ ) 
  for ( j = 0; j < N; j++ )
  for ( k = 0; k < N; k++ )
    if(dist[i][j] && dist[j][k])
      dist[i][k]=1;

The result of violating the property is that the transitive closure paths grow (at worst) only one link in the O(n^3) iterations above. In order to ensure that they transitive closure paths grow all the way, we need to keep iterating until they stop growing:

do{
  something_done=false;
  for ( i = 0; i < N; i++ ) 
  for ( j = 0; j < N; j++ )
  for ( k = 0; k < N; k++ )
    if(dist[i][j] && dist[j][k]){
      dist[i][k]=1;
      something_done=true;
    }
} while (something_done);

If the outer loop is in O(N), then the algorithm itself is in O(N^4).

Unfortunately, it may not be possible to (easily) show that the outer loop has that property, since it is particular to the data.