Warshall's algorithm for transitive closure

Question

I was going through this code for implementing Warshall's algorithm. I think the time complexity for this simple problem is huge because there are too many loops running here. The time complexity for this code should be \$O(n^3)\$.

Is there a way to optimize this code so that the time complexity can be reduced a bit?

#include<stdio.h>
#include<unistd.h>
#include<math.h>
int maximum(int,int);
void warshal(int p[10][10],int n)
{
int i,j,k;

for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
   for(k=1;k<=n;k++)
     p[i][j]=maximum(p[i][j],p[i][k]&&p[k][j]);
}
int maximum(int a,int b)
{                                                       ;
if(a>b)
return(a);
else
return(b);
}
void main()
{
int p[10][10]={0},n,e,u,v,i,j;

 printf("\n Enter the number of vertices:");
 scanf("%d",&n);

 printf("\n input values now\n");
 for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
   scanf("%d",&p[i][j]);

   printf("\n Matrix of input data: \n");
 for(i=1;i<=n;i++)
 {
   for(j=1;j<=n;j++)
 printf("%d\t",p[i][j]);
 printf("\n");
 }
 warshal(p,n);
 printf("\n Transitive closure: \n");
 for(i=1;i<=n;i++)
 {
 for(j=1;j<=n;j++)
 printf("%d\t",p[i][j]);
 printf("\n");
 }
  }

Answer 1

Arrays are 0-indexed

In C, arrays are 0-indexed. Not 1-indexed. So you're skipping the first element and running off the back in these loops. You want:

for(i=0;i<n;i++)
  for(j=0;j<n;j++)
    for(k=0;k<n;k++)

Use braces

Nested logic is crying for braces to make it easer to read:

for(i=0;i<n;i++) {
  for(j=0;j<n;j++) {
    for(k=0;k<n;k++) {
    }
  }
}

That'll also future proof anything else you add into these loops. What if you added logging? You'd have to go back and add braces then anyway. It's a good habit to get into. Always braces.

maximum()

There's actually no reason for this function. The logic you want is:

R(k)[i, j] = R(k-1)[i, j] or (R(k-1)[i,k] and R(k-1)[k,j])

We can just do that directly using bitwise math:

for(i=0;i<n;i++) {
  for(j=0;j<n;j++) {
    for(k=0;k<n;k++) {
      p[i][j] = p[i][j] | (p[i][k] & p[k][j]);
    }
  }
}

Answer 2

Bug

The order of your loops is wrong. This session demonstrates the error:

 Enter the number of vertices:3

 input values now
0 0 1
1 0 0
0 1 0

 Matrix of input data:
0       0       1
1       0       0
0       1       0

 Transitive closure:
0       1       1
1       1       1
1       1       1

The correct order of the loops is k, i, j:

for(k=1;k<=n;k++)
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            p[i][j] |= p[i][k] & p[k][j];

Which gives the correct result for the previous input:

 Transitive closure:
1       1       1
1       1       1
1       1       1

Time complexity

The time complexity of your program is clearly \$O(n^3)\$ due to your three nested loops. Since this is the expected time complexity of Warshall's algorithm, I'm not sure why you think you have "too many loops".

Answer 3

• Use a tool to indent the code properly.
• Simplify maximum using ternary:

int maximum(int a,int b)
{
    return a > b ? a : b;
}

• Use C99 and declare variables inside loops, like:

for(int i=1;i<=n;i++)

• Put spaces around operators for readability.

• Always use braces, especially for nested loops like:

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
p[i][j]=maximum(p[i][j],p[i][k]&&p[k][j]);

• Use puts instead of printf when there is no formatting.

• Use a constant int p[10][10] <-- Where does 10 come from, what does it mean, what happens if I change it? Give it a name like MAXIMUM_MATRIX_SIZE

• Compile using the -pedantic flag and fix all the warning, to me compiling your program gives:

war.c:20:6: warning: return type of ‘main’ is not ‘int’ [-Wmain]
 void main()
      ^
war.c: In function ‘main’:
war.c:27:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ^
war.c:31:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&p[i][j]);
     ^