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结果错误。
修复方案
替换错误的路径回溯逻辑,采用递归方式完整打印所有中转节点:
- 新增路径打印函数
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); }
- 修改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
相关产品推荐
相关产品推荐

