c++ - Floyd-Warshall STP 实现

Question

我对 Floyd-Warshall 算法有疑问。如果输入有超过 4 个顶点，它就不起作用。为了制作二维动态数组，我制作了一个动态数组 [N*N] 并访问 A[i,j] = A[(i-1)*N+j]

void floyd_Algorithm(fstream &F2,int N,int matrixGraph[],int matrixP[])
{
for (int k=1; k<=N; k++)
    for (int i=1; i<=N; i++)
        for (int j=1; j<=N; j++)
        {
            if (matrixGraph[(i-1)*N+j] > matrixGraph[(i-1)*N+k] + matrixGraph[(k-1)*N+j])
            {
                matrixGraph[(i-1)*N+j] =  matrixGraph[(i-1)*N+k] + matrixGraph[(k-1)*N+j];
                matrixP[(i-1)*N+j] = k ;
            }
}

这里是4个顶点矩阵的输入

4

0 10 6 2| 10 0 5 3 | 6 5 0 1| 2 3 1 0|

输出

0 5 3 2
5 0 4 3
3 4 0 1
2 3 1 0

1 4 4 1
4 2 4 2
4 4 3 3
4 4 4 4

7个顶点矩阵输入

7

0 3 6 0 0 0 0| 3 0 2 4 0 0 0| 6 2 0 1 4 2 0 | 0 4 1 0 2 0 4| 0 0 4 2 0 2 1| 0 0 2 0 2 0 1| 0 0 0 4 1 1 0|

输出

0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

1 5 7 1 1 1 1
5 2 7 5 2 2 2
7 7 3 7 7 7 3
4 5 7 4 1 4 1
5 5 7 1 5 1 1
6 6 7 6 1 6 1
7 7 7 1 1 1 7

Answer 1

你的索引有问题。

如果你的顶点在 1 <= v <= N 的范围内，那么 i 和 j 之间的路径应该是矩阵[(i-1)*N+j-1]

为避免错误，您可能应该将顶点保持在 0 <= v < N 的范围内，因为 (int i = 0; i < N; i++), matrix[i*N+j]