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

sususususu

#include<stdio.h>
#define Max 0xFFFF
#define n 38

void floyd(int graph[n][n])//弗洛伊德求各顶点之间的最短路径
{
        int dist[n][n];
        for (int i = 0; i < n; i++)//初始化距离矩阵
        {
                for (int j = 0; j < n; j++)
                        dist[i][j] = graph[i][j];
        }
        for (int k = 0; k < 38; k++)//逐一考虑每个顶点作为中间顶点
        {
                for (int i = 0; i < 38; i++)//
                {
                        for (int j = 0; j < 38; j++)
                        {
                                if (dist[i][j] > dist[i][k] + dist[k][j])//k作为中间顶点，可以缩短（i，j）的距离
                                        dist[i][j] = dist[i][k] + dist[k][j];
                        }
                }
        }
        for (int i = 0; i < 38; i++)
        {
                for (int j = 0; j < 38; j++)
                {
                        printf("%4.1f", dist[i][j]);
                }
                printf("\n");
        }
}

int main()
{
        int graph[n][n] = { {0,6,13},{10,0,4} ,{5,Max,0} };
        floyd(graph);
        return 0;
}

为什么输出均为0？

最佳答案

月排行榜 / 总排行榜

sfqxx

2023-12-18 17:30:23

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

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

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

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

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

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

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

跳转到最佳答案楼层

FishC

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

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

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

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

修正后的代码如下所示：

#include <stdio.h>#define Max 0xFFFF#define n 38void floyd(int graph[n][n])//弗洛伊德求各顶点之间的最短路径{    int dist[n][n];    for (int i = 0; i < n; i++)//初始化距离矩阵    {        for (int j = 0; j < n; j++)            dist[i][j] = graph[i][j];    }    for (int k = 0; k < n; k++)//逐一考虑每个顶点作为中间顶点    {        for (int i = 0; i < n; i++)        {            for (int j = 0; j < n; j++)            {                if (dist[i][j] > dist[i][k] + dist[k][j])//k作为中间顶点，可以缩短（i，j）的距离                    dist[i][j] = dist[i][k] + dist[k][j];            }        }    }    for (int i = 0; i < n; i++)    {        for (int j = 0; j < n; j++)        {            printf("%4d", dist[i][j]);        }        printf("\n");    }}int main(){    int graph[n][n] = {        {0,   6,   13},        {10,  0,   4},        {5,   Max, 0}    };    floyd(graph);    return 0;}

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

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

sfqxx

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

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

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

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

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

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

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

sususususu

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

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

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