# Warshall's algorithm for transitive closure

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");
}
}

• Well, Warshall's algorithm is Theta(n^3), so how do you expect to improve on that without changing the algorithm? Oct 2 '15 at 17:26
• @user3629249 Do you want to actually write an answer, or are you just going to keep writing comments? Oct 2 '15 at 17:54
• @Barry, None of my comments are an answer. nor do they address the question about reducing the O factor. The comments are to the OP regarding how to present the code for easy readability and injecting a bit of reality into asking the user to input up to 101 numeric entries and the advisability of checking for error conditions when inputting data from the user.. SO, yes, I will continue to comment Oct 2 '15 at 18:16
• @user3629249 Then I recommend you take the tour and note that "Use comments to ask for more information or clarify a question or answer" You are providing a code review, which bears a remarkable similarity to the name of the site. So much so that it's almost like that's what the answers on this site are supposed to do... Oct 2 '15 at 18:20

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]);
}
}
}


# 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".

• 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]);
^