0

基本上，我的任务是实现 Floyd 算法来找到矩阵的最短路径。在我的例子中，一个值 arg 被输入，矩阵变成大小 arg*arg。下一串值按接收顺序应用于矩阵。最后，a -1 代表无穷大。

老实说，我不知道我的问题出在哪里。通过测试时，第一对通过了，但其余的都失败了。我只会发布前两次失败以及通行证。我只会发布相关的代码段。

int arg, var, i, j;

cin >> arg;

int arr[arg][arg];

for (i = 0; i < arg; i++)
{
    for(j = 0; j < arg; j++)
    {
        cin >> var;
        arr[i][j] = var;
    }
}


for(int pivot = 0; pivot < arg; pivot++)
{
    for(i = 0; i < arg; i++)
    {
        for(j = 0; j < arg; j++)
        {
            if((arr[i][j] > (arr[i][pivot] + arr[pivot][j])) && ((arr[i][pivot] != -1) && arr[pivot][j] != -1))
            {
                arr[i][j] = (arr[i][pivot] + arr[pivot][j]);
                arr[j][i] = (arr[i][pivot] + arr[pivot][j]);
            }
        }
    }
}

这是我收到的失败。其余的变得越来越长，最多为 20*20 矩阵，所以我将不再赘述：

floyd> 
 * * * Program successfully started and correct prompt received. 

floyd 2 0 14 14 0
0 14 14 0 
floyd>   PASS  : Input "floyd 2 0 14 14 0" produced output "0 14 14 0".  

floyd 3 0 85 85 85 0 26 85 26 0
0 85 85 85 0 26 85 26 0 
floyd>   PASS  : Input "floyd 3 0 85 85 85 0 26 85 26 0" produced output "0 85 85 85 0 26 85 26 0".  

floyd 3 0 34 7 34 0 -1 7 -1 0
0 34 7 34 0 -1 7 -1 0 
floyd>   FAIL  : Input "floyd 3 0 34 7 34 0 -1 7 -1 0" did not produce output "0 34 7 34 0 41 7 41 0".  

floyd 4 0 -1 27 98 -1 0 41 74 27 41 0 41 98 74 41 0
0 -1 27 68 -1 0 41 74 27 41 0 41 68 74 41 0 
floyd>   FAIL  : Input "floyd 4 0 -1 27 98 -1 0 41 74 27 41 0 41 98 74 41 0" did not produce output "0 68 27 68 68 0 41 74 27 41 0 41 68 74 41 0".
4

1 回答 1

0

想象一下这种情况arr[i][j] == -1，显然(arr[i][j] > (arr[i][pivot] + arr[pivot][j])) && ((arr[i][pivot] != -1) && arr[pivot][j] != -1)失败了，但它不应该arr[i][pivot]和arr[pivot][j]不是-1

由于您使用-1的是无穷大而不是无穷大，因此您必须有类似的东西，if ((arr[i][j] == -1 || arr[i][j] > (arr[i][pivot] + arr[pivot][j])) && ((arr[i][pivot] != -1) && arr[pivot][j] != -1))即检查两件事：第一个是您的条件，第二个arr[i][j]是无穷大并且pivot存在路径的情况，在这种情况下，任何有效路径小于无穷大。

于 2014-04-11T01:27:34.023 回答