[已解决]弗洛伊德算法输出问题

sususususu

1. #include<stdio.h>
   
2. #define Max 0xFFFF
   
3. #define n 38
   
4. 
   
5. void floyd(int graph[n][n])//弗洛伊德求各顶点之间的最短路径
   
6. {
   
7.         int dist[n][n];
   
8.         for (int i = 0; i < n; i++)//初始化距离矩阵
   
9.         {
   
10.                 for (int j = 0; j < n; j++)
    
11.                         dist[i][j] = graph[i][j];
    
12.         }
    
13.         for (int k = 0; k < 38; k++)//逐一考虑每个顶点作为中间顶点
    
14.         {
    
15.                 for (int i = 0; i < 38; i++)//
    
16.                 {
    
17.                         for (int j = 0; j < 38; j++)
    
18.                         {
    
19.                                 if (dist[i][j] > dist[i][k] + dist[k][j])//k作为中间顶点，可以缩短（i，j）的距离
    
20.                                         dist[i][j] = dist[i][k] + dist[k][j];
    
21.                         }
    
22.                 }
    
23.         }
    
24.         for (int i = 0; i < 38; i++)
    
25.         {
    
26.                 for (int j = 0; j < 38; j++)
    
27.                 {
    
28.                         printf("%4.1f", dist[i][j]);
    
29.                 }
    
30.                 printf("\n");
    
31.         }
    
32. }
    
33. 
    
34. int main()
    
35. {
    
36.         int graph[n][n] = { {0,6,13},{10,0,4} ,{5,Max,0} };
    
37.         floyd(graph);
    
38.         return 0;
    
39. }

复制代码

为什么输出均为0？

最佳答案

月排行榜 / 总排行榜

sfqxx

2023-12-18 17:30:23

这种情况下，程序输出为零是因为矩阵的声明和初始化有误。

在main函数中，矩阵的初始化方式有问题，你的目的肯定是想给一个3x3的矩阵进行初始化，但实际上你给的矩阵只在一部分区域进行了初始化，其他区域被隐式地初始化为零了。同时你在floyd函数中对于i和j的遍历上限都采用了常数38，远大于你的实际矩阵规模。

将main函数下的矩阵声明和初始化修改如下：

1. 
   
2. int main()
   
3. {
   
4.     int graph[3][3] = { {0,6,13},{10,0,4} ,{5,Max,0} };
   
5.     floyd(graph);
   
6.     return 0;
   
7. }

复制代码

然后将floyd函数的4个循环数修改为

1. for (int k = 0; k < 3; k++)
   
2. for (int i = 0; i < 3; i++)
   
3. for (int j = 0; j < 3; j++)

复制代码

由于你只有3x3的矩阵，故只需遍历3次。这样，你的程序就应该能产生正确的输出了。

跳转到最佳答案楼层

FishC

您的代码有几个问题导致输出都为0：

1. 在初始化距离矩阵时，没有正确赋值给`dist`变量。应该将`dist = graph[j]`。

2. 在主循环中，计算最短路径时，用到了错误的距离参量。应该将`dist`改为`graph[k]+graph[k][j]`。

3. 在输出结果时，使用了错误的变量`dist`，应该输出`graph[j]`。

修正后的代码如下所示：

1. #include <stdio.h>
2. #define Max 0xFFFF
3. #define n 38
5. void floyd(int graph[n][n])//弗洛伊德求各顶点之间的最短路径
6. {
7.     int dist[n][n];
8.     for (int i = 0; i < n; i++)//初始化距离矩阵
9.     {
10.         for (int j = 0; j < n; j++)
11.             dist[i][j] = graph[i][j];
12.     }
13.     for (int k = 0; k < n; k++)//逐一考虑每个顶点作为中间顶点
14.     {
15.         for (int i = 0; i < n; i++)
16.         {
17.             for (int j = 0; j < n; j++)
18.             {
19.                 if (dist[i][j] > dist[i][k] + dist[k][j])//k作为中间顶点，可以缩短（i，j）的距离
20.                     dist[i][j] = dist[i][k] + dist[k][j];
21.             }
22.         }
23.     }
24.     for (int i = 0; i < n; i++)
25.     {
26.         for (int j = 0; j < n; j++)
27.         {
28.             printf("%4d", dist[i][j]);
29.         }
30.         printf("\n");
31.     }
32. }
34. int main()
35. {
36.     int graph[n][n] = {
37.         {0,   6,   13},
38.         {10,  0,   4},
39.         {5,   Max, 0}
40.     };
41.     floyd(graph);
42.     return 0;
43. }

复制代码

修正后的代码中，修正了距离矩阵的赋值以及计算最短路径的错误，并且输出结果已改为打印`dist`而不是原本的`graph`。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

sfqxx

这种情况下，程序输出为零是因为矩阵的声明和初始化有误。

在main函数中，矩阵的初始化方式有问题，你的目的肯定是想给一个3x3的矩阵进行初始化，但实际上你给的矩阵只在一部分区域进行了初始化，其他区域被隐式地初始化为零了。同时你在floyd函数中对于i和j的遍历上限都采用了常数38，远大于你的实际矩阵规模。

将main函数下的矩阵声明和初始化修改如下：

1. 
   
2. int main()
   
3. {
   
4.     int graph[3][3] = { {0,6,13},{10,0,4} ,{5,Max,0} };
   
5.     floyd(graph);
   
6.     return 0;
   
7. }

复制代码

然后将floyd函数的4个循环数修改为

1. for (int k = 0; k < 3; k++)
   
2. for (int i = 0; i < 3; i++)
   
3. for (int j = 0; j < 3; j++)

复制代码

由于你只有3x3的矩阵，故只需遍历3次。这样，你的程序就应该能产生正确的输出了。

sususususu

sfqxx 发表于 2023-12-18 17:30
这种情况下，程序输出为零是因为矩阵的声明和初始化有误。

在main函数中，矩阵的初始化方式有问题，你的 ...

可是我对一部分区域进行初始化，按理说输出也不会都为0呀