You need to enable JavaScript to run this app. Floyd算法计算最短路径时path[0][7]结果错误原因咨询
优惠活动
大模型
产品
解决方案
定价
更多

Floyd算法计算最短路径时path[0][7]结果错误原因咨询

问题原因分析
  • path数组设计逻辑理解偏差
    Floyd算法中path[i][j]存储的是i到j最短路径上的中转节点,而非终点j的直接前驱节点。你预期path[0][7]为4,本质是把path数组当成了前序节点数组来用,这和当前代码的path设计逻辑不符。
    当前代码中转点k的遍历顺序是从0到9,当k=4时,仅能得到中转点不超过4的临时最短路径0→1→2→4→7,总权值为20,path[0][7]此时会被临时设为4;当k=5时,D[0][5] + D[5][7] = 8 +7=15小于20,因此D[0][7]会更新为最短的15,path[0][7]被设置为5,后续没有更短的路径,因此最终path[0][7]为5是符合当前代码逻辑的正常结果,D矩阵权值无错误也验证了最短路径长度是正确的。
  • 路径回溯逻辑存在错误
    你当前的路径回溯代码只处理了起点到中转节点的路径,完全漏掉了中转节点到终点的路径:
while( path[v1][v2] != -1 ){
    printf("%d<-", Graph->Data[path[v1][v2]] );
    v2 = path[v1][v2];
}

以path[0][7]=5为例,你把v2设置为5后,就不会再处理5到7之间的中转节点4,因此才会看不到你预期的节点4,误以为path结果错误。

修复方案

替换错误的路径回溯逻辑,采用递归方式完整打印所有中转节点:

  1. 新增路径打印函数
void PrintPath(Vertex path[][MaxVertexNum], Vertex start, Vertex end, DataType Data[]) {
    if (path[start][end] == -1) {
        return;
    }
    PrintPath(path, path[start][end], end, Data);
    printf("%d<-", Data[path[start][end]]);
    PrintPath(path, start, path[start][end], Data);
}
  1. 修改main函数中的路径输出部分
// 替换原有的while循环输出逻辑
printf("%d<-", Graph->Data[V2]);
PrintPath(path, V1, V2, Graph->Data);
printf("%d", Graph->Data[V1]);

修改后运行即可得到完整路径7<-4<-5<-3<-1<-0,和你预期的路径节点完全一致。

内容的提问来源于stack exchange,提问作者NAUGHTYCat

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.15 22:45:03