CODEWITHSUNDEEP
c++algorithmshortest-pathfloyd-warshall
user1077685
user1077685

Reputation:

What is wrong with my C++ Floyd's all-pairs shortest paths program?

I am trying to find the all-pairs shortest paths matrix for a 5x5 matrix, but the output is not showing the right answer.

Here is the initial matrix and my output:

enter image description here

Here is the actual solution though:

[0, 2, 3, 1, 4, 

6, 0, 3, 2, 5

10, 12, 0, 4, 7,

6, 8, 2, 0, 3,

3, 5, 6, 4, 0]

As you can see, it reads the initial matrix correctly, but somewhere in the code, the math isn't being applied correctly, or something is messing up.

Below is my code, can you find my mistakes?

int matrixFloyd(int *C, int n, int *A, string* s)
{

  int i,j,k;

  for (i=0; i<n; i++)
  {
    for (j=0; j<n; j++)
    {
      if ( *(C+i*n+j) == -1)
      {
        *(A+i*n+j) = 999999999;
      }
      else
      {
        *(A+i*n+j) = 1;
        char sz[3]="";
        sprintf(sz,"%d",j+1);
        s[i*n+j]=sz;
      }
    }
  }

  for (i=0; i<n; i++)
  {
    *(A+i*n+i) = 0;
  }

  for (k=0; k<n; k++)
  {
    for (i=0; i<n; i++)
    {
      for (j=0; j<n; j++)
      {
        if ( *(A+i*n+k) + *(A+k*n+j) < *(A+i*n+j) )

          // A[i][j] = A[i][k] + A[k][j];
          *(A+i*n+j) = *(A+i*n+k)+ *(A+k*n+j);
      }
    }
  }

  return 0;
}

Upvotes: 0

Views: 777

Answers (1)

Pablo
Pablo

Reputation: 8644

You're ignoring the original C values:

*(A+i*n+j) = 1;

Should be

*(A+i*n+j) = *(C+i*n+j);

Upvotes: 2

Related Questions