4
\$\begingroup\$

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");
 }
  }
\$\endgroup\$
4
  • \$\begingroup\$ Well, Warshall's algorithm is Theta(n^3), so how do you expect to improve on that without changing the algorithm? \$\endgroup\$
    – Barry
    Oct 2 '15 at 17:26
  • 2
    \$\begingroup\$ @user3629249 Do you want to actually write an answer, or are you just going to keep writing comments? \$\endgroup\$
    – Barry
    Oct 2 '15 at 17:54
  • 1
    \$\begingroup\$ @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 \$\endgroup\$ Oct 2 '15 at 18:16
  • 2
    \$\begingroup\$ @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... \$\endgroup\$
    – Barry
    Oct 2 '15 at 18:20
2
\$\begingroup\$

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]);
    }
  }
}
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$
  • 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]);
     ^
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.