c++ - 我的 C++ Floyd 的全对最短路径程序有什么问题？

Question

我正在尝试查找 5x5 矩阵的所有对最短路径矩阵，但输出未显示正确答案。

这是初始矩阵和我的输出：

这是实际的解决方案：

[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]

如您所见，它正确读取了初始矩阵，但在代码中的某处，数学没有被正确应用，或者有些东西搞砸了。

下面是我的代码，你能找到我的错误吗？

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

Answer 1

您忽略了原始 C 值：

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

应该

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