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

• Barry: Well, Warshall's algorithm is Theta(n^3), so how do you expect to improve on that without changing the algorithm?
• Barry: @user3629249 Do you want to actually write an answer, or are you just going to keep writing comments?
• user3629249: @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
• Barry: @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...

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