# 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,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={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, 2015 at 17:26
• @user3629249 Do you want to actually write an answer, or are you just going to keep writing comments? Oct 2, 2015 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, 2015 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, 2015 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 <-- 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]);
^