校园导航Floyd最短路径：路径倒序与INF坑点排查

简介面向计算机专业学生与数据结构初学者的一份课程设计参考文档围绕「校园导航系统」这一经典图论题目展开可用于课程设计选题、实验报告撰写或算法复习时对照思路。压缩包内共1个doc文件体积约187KB即《数据结构课程设计-校园导航系统》完整设计报告含任务书、详细设计、调试测试、时间复杂度分析、源程序清单与执行结果、程序设计总结、致谢与参考文献等章节。报告以邻接矩阵存储校园平面图用顺序表保存景点的名称、代号与简介边记录路径长度并采用Floyd算法求解任意两点间最短路径对Dijkstra、Bellman-Ford等算法的适用场景也有辨析还讨论了邻接表与邻接矩阵的取舍以及C语言实现的要点。调试部分记录了最短路径输出只能正序等问题及解决过程测试结果分析与复杂度说明可帮助读者理解验证方法。目前已有67人学习适合需要一份可直接参照的课程设计范本或图算法实践案例的读者。1. 从食堂到图书馆能跑通、反过来就少一半景点说起校园导航系统这份数据结构课程设计几乎每个人的代码都能编译通过、能查景点简介、能弹出菜单最后卡住的地方出奇一致最短路径算得对打印出来的顺序是反的。我见过太多份报告测试截图里从学生第二食堂到图书馆是「食堂——操场——博学楼——图书馆」从图书馆回食堂就只剩「图书馆——食堂」两跳中间节点凭空消失。这类问题不报错、不崩溃编译器一句警告都不给只能人肉比对路径折腾起来最费时间。这份资源用邻接矩阵存图、Floyd 求全源最短路坑点集中在 path 表的用法、中文输入和权值边界这三处。如果你正卡在路径倒着走、查询查不到、距离算出 1000 这三类现象上下面这套顺序可以直接照着排查。2. 路径打印成倒序Floyd 的 path 表到底该往前收还是往后收2.1 现象正着查对、反着查只剩两头先看现场。景点数组里下标 0 到 9 依次是学生第二食堂、男生宿舍、操场、物理楼、博学楼、草地、老教、女生宿舍、小门、图书馆。手算一遍从食堂0到图书馆9最短路是 0→2→4→5→8→6→9总长 3030108255走的是操场、博学楼、草地、小门、老教。把起点终点调过来查 9→0屏幕上只剩下两行字图书馆——学生第二食堂中间五个景点一个都不见了但距离显示的还是一百多。这就不是 Floyd 算错了算法算出来的距离是对的错的是从 path 表还原路径那一段。判断方法很干脆把 weight 表打出来看一眼如果weight[9][0]的数值仍然是那个正确的距离说明矩阵没问题问题全在打印逻辑如果weight[9][0]直接等于无穷大那是图本身没连上第 4 章再处理。2.2 path[i][j] 存的是中转点不是“前驱”最常见的误解是把path[i][j]当成「j 的前一个点」去用照着单源 Dijkstra 的 pre 数组习惯来遍历一顺一逆就会错位。Floyd 的 path 表语义完全不同/* cost: 原始邻接矩阵全程只读weight: 最短距离结果表path: 中转点表 */ void Floyd(int cost[][MaxVertices], int n, int weight[][MaxVertices], int path[][MaxVertices]) { int i, j, k; for (i 0; i n; i) for (j 0; j n; j) { weight[i][j] cost[i][j]; /* 复制一份原图后面还要用 */ path[i][j] -1; /* -1 表示 i 到 j 直达无中转 */ } for (k 0; k n; k) /* 中转点必须在最外层 */ for (i 0; i n; i) for (j 0; j n; j) if (weight[i][k] ! INF weight[k][j] ! INF weight[i][j] weight[i][k] weight[k][j]) { weight[i][j] weight[i][k] weight[k][j]; path[i][j] k; /* 只记下最后一次生效的中转点 */ } }path[i][j] k的含义是「i 到 j 的最短路上途经了 k 这个顶点」而不是「j 前面那个点是 k」。参数上n传的是顶点个数而不是边数cost必须保留原始值不能就地覆盖否则第二次调用查询时拿到的是已经求过最短路的矩阵再算一遍结果就飘了。这也是为什么要多开一张weight表。原文里那段回溯代码之所以时对时错根子在于它拿j、k两个变量一边当坐标、一边当路径游标while (m ! -1) { value[count] m; if (j k) k m; /* 起点终点下标被就地改写 */ else j m; m path[j][k]; count; }j和k原本存的是起点和终点的下标用来判断「谁大谁小」以决定打印方向。循环里又把它们改成路径上的中间点下一次path[j][k]查的就已经不是原来那条路径了。起点下标比终点下标小的时候恰好凑巧能走通反过来就散架——这正是 2.1 里那个现象的来源。2.3 改法一递归回溯十几行写清楚把「拆路径」和「打印方向」这两件事分开最省事的写法是递归/* 递归打印 s 到 t 的路径调用前保证 path 表已由 Floyd 填好 */ void printPath(int path[][MaxVertices], int s, int t, SeqList *v) { int k path[s][t]; if (k -1) { /* 直达不需要再拆 */ printf(%s - , v-list[s].name); return; } printPath(path, s, k, v); /* 先走 s 到 k 这一段 */ printPath(path, k, t, v); /* 再走 k 到 t 这一段 */ }逻辑是分治s到t的最短路经过k那就先解决s到k再解决k到t递归出口是path[s][t] -1。整个过程只读取path不修改任何坐标变量所以不可能出现正反向不一致。参数说明两点。第一v指向存景点的顺序表用来把下标翻译成名字传指针避免整个结构体拷贝。第二递归深度上界是顶点数n校园导航这种十几二十个点的规模完全不用担心爆栈但如果哪天把景点扩到几百个还是换 2.4 的迭代写法稳当。调用侧要补一个终点。上面这个函数只负责打印除终点外的所有节点主流程里补一句printf(%s, v-list[s].name); printPath(path, s, t, v); /* 打印 s 之后的所有中间点 */ printf(%s\n, v-list[t].name); /* 单独补上终点 */2.4 改法二数组回填加逆序输出不依赖递归如果不想用递归思路是固定起点、把终点一路往回挪挪一步压一次栈最后整体出栈/* 迭代版路径打印固定起点 s终点 j 沿 path 链向 s 收缩 */ void printPathStack(int path[][MaxVertices], int s, int t, SeqList *v) { int stack[MaxVertices], top 0, k, j t; if (s t) { /* 起点等于终点要单独处理 */ printf(%s\n, v-list[s].name); return; } printf(%s, v-list[s].name); while ((k path[s][j]) ! -1) { /* 查的是 path[s][j]s 始终不动 */ stack[top] k; j k; /* 终点往前收一格 */ } while (top 0) /* 栈顶离起点最近先出 */ printf( - %s, v-list[stack[--top]].name); printf( - %s\n, v-list[t].name); }关键在于s从头到尾没被改过。栈里存进去的顺序是「离终点近的先压」出栈时自然变成「离起点近的先出」这就是正序。t单独保留是因为循环结束时j已经退到了s附近不再是终点直接拿j打印会少一个节点。两种改法的取舍很明确递归版短、好读适合写进报告迭代版不依赖函数调用栈景点数量往大了扩也不怕。我个人倾向报告里写递归版答辩老师一眼能看懂副本里留迭代版防翻车。2.5 三组必跑用例专治“看起来对了”改完别急着截图交报告按这三组过一遍覆盖的都是容易漏的分支起点终点期望输出卡住什么问题学生第二食堂图书馆食堂→操场→博学楼→草地→小门→老教→图书馆多中转点正序路径不该缺中间节点图书馆学生第二食堂图书馆→老教→小门→草地→博学楼→操场→食堂反向还原正是 2.1 的原始故障学生第二食堂学生第二食堂只输出一个名字起点等于终点递归版会重复打印男生宿舍物理楼宿舍→物理楼直达path -1分支不加这句会打出空行第三组特别容易被忽略。递归版里如果没在调用前判s tpath[s][s]是 -1函数会直接打印起点然后返回主流程再补一次终点屏幕上就出现「食堂 - 食堂」。距离是 0看着不算错但放进报告截图里就很扎眼。3. 提示“您所查询的景点不在范围内”中文串比较与输入缓冲的四个坑3.1 名字看着一模一样strcmp 就是不返回 0这是最高频的求助场景控制台敲「图书馆」三个字程序说找不到把景点数组打印出来比对怎么看都一致。原因往往有三个层面。一是源码里的字符串本身带全角符号。原文那段景点初始化数组就长这样DataType a[]{{“学生第二食堂,10,学生的主要就餐点}, ... };左边那个引号是全角「“」右边是半角。全角引号在编译器眼里是非法字符多数编译器会报stray \357 in program或者一串C2018: 未知字符但有些老编译器只是警告于是程序带着一段诡异的字节流跑起来了strcmp自然永远不相等。二是从 Word 文档里复制景点名带进了不可见字符。全角空格、零宽空格、BOM 头这些都很常见肉眼完全看不出来strlen一算却多了两三个字节。三是控制台代码页和源文件编码不一致手动输入的中文和源码里的中文在内存中根本不是同一串字节。应对办法有三条按省事程度排优先改成输入景点编号1 到 10来选景点彻底绕开中文比对其次在比较前把两边的空白字符含全角空格\xE3\x80\x80剥掉最后才是逐字节 dump 出来看十六进制。# 找出源码里混进来的全角引号、全角逗号、全角括号 grep -nP [\x{2018}\x{2019}\x{201C}\x{201D}\x{FF0C}\x{FF1B}\x{FF08}\x{FF09}] school.cpp这条命令依赖 GNU grep 的-P选项Windows 上如果用的是自带 findstr 或者精简版 grep 会不认可以换成grep -n [“”]直接敲中文效果一样。跑完有输出就说明源码里确实有全角符号逐个改回 ASCII 即可。提示改完编译过了也别急着信全角符号有时候藏在注释里不报错但藏进字符串就会让你查半小时。3.2 scanf(%s) 遇到带空格的景点名直接截断「学生第二食堂」没有空格所以没事但校园里叫「东区 大门」「老教 后门」这种带空格的景点一抓一把。scanf(%s)读到空格就停剩下的半个名字留在输入缓冲区里被下一次scanf当成新输入读走表现出来就是「输入了一个名字程序却查了两次」。统一的解法是把所有字符串输入换成fgets再手工去掉行尾换行/* 读一行景点名到 buf去掉行尾的 \n 和 \r返回长度0 表示空行 */ int readName(char *buf, int size) { size_t len; if (fgets(buf, size, stdin) NULL) return 0; len strlen(buf); if (len 0 buf[len - 1] \n) buf[len - 1] \0; /* 先剥 \n */ len strlen(buf); /* 长度要重算 */ if (len 0 buf[len - 1] \r) buf[len - 1] \0; /* 再剥 \r */ return (int)strlen(buf); }这里有个细节值得单独说剥完\n之后必须重新strlen否则紧接着判\r用的还是旧长度会把最后一个正常字符当成回车删掉。Windows 下的换行是\r\n两个字节Linux 下只有一个\n同一份代码两边跑不处理这个差异就会出现「Linux 正常、Windows 少一个字」的玄学现象。size参数传缓冲区大小fgets最多读size - 1个字符并补\0所以不会越界。缺点是超长输入会被截断并留在缓冲区里需要额外的清空逻辑景点名一般也就七八个字20 字节的缓冲区够用。3.3 查找函数别让调用方猜返回值把「按名字找下标」抽成一个函数返回 -1 表示没找到调用方必须判/* 按景点名查下标找到返回下标找不到返回 -1 */ int findVertex(AdjMGraph *G, const char *name) { int i; for (i 0; i G-vertices.size; i) if (strcmp(G-vertices.list[i].name, name) 0) return i; return -1; }原实现用的是「循环变量 i 走完整个表就等于没找到」这种隐式约定。写法本身不算错但一旦有人在循环里加了break或者漏了break这个约定立刻失效——漏break会重复打印所有匹配项多加break又可能把「第几项」算错。返回 -1 的好处是调用方能写出一行防御if (j 0 || k 0) { printf(景点名有误请检查是否输错了字\n); return; /* 千万别带着 -1 继续往下算 */ }漏了这个判断G.vertices.list[-1].name就是一次越界读表现可能是打印出一串乱码也可能直接段错误而且崩的位置往往离出错点很远典型的那种查半天查不到源头的黑匣子故障。3.4 找不到时输出的提示语本身也要能区分「您所查询的景点不在我们所提供的范围内」这句话对用户不友好对排查也不友好——它没告诉你到底是名字打错了还是表里压根没这个景点。判断成本最低的改法是提示时把可选范围带上printf(未找到「%s」可选景点, name); for (i 0; i G-vertices.size; i) printf(%s(%d) , G-vertices.list[i].name, G-vertices.list[i].code); printf(\n);带上编号之后用户能立刻发现是自己少打了一个字还是这个景点根本没录进数组。后面第 4 章要讲的「图没连上」也能靠这句话排除掉一半可能能查到景点说明顶点表没问题那就只剩边的问题了。4. 距离算出 1000 甚至更大无穷大取值与邻接矩阵对称性4.1 输出的 1000 不是距离是“走不到”#define MaxWeight 1000这个宏在大多数课设里都被当成「无穷大」。问题在于它只是个普通整数程序里没有任何地方告诉它「你代表不可达」。于是当两个景点之间压根没有通路时weight[i][j]原封不动保留 1000打印函数照常输出「最短路径为1000」看起来像条一千米的路其实根本走不过去。正确的做法是把判断显式写出来if (weight[j][k] INF) { printf(%s 到 %s 之间没有通路\n, name1, name2); return; } printf(最短路径为 %d\n, weight[j][k]);INF就是那个宏常量。判断条件用而不是因为有些实现会把不可达标成 999、0x3f3f3f3f 之类的不同值用能一并兜住。4.2 INF 取多大才不参与加法溢出Floyd 的核心是一次松弛weight[i][j] weight[i][k] weight[k][j]。如果weight[i][k]和weight[k][j]都是「无穷大」两者相加就得到一个更大的数。用 1000 当无穷大时100010002000没溢出 int但会造出一个 2000 的「假距离」如果哪天为了表示「特别远」把宏改成 100000两条不可达边相加就是 200000仍然没溢出但要是有人图省事写成INT_MAXINT_MAX INT_MAX直接是未定义行为结果可能是负数——屏幕上出现「最短路径为-2147483648」这是这条路上最经典的一帧。稳妥的写法是取一个「加两次也不溢出且远大于任何真实路径」的值#define INF 0x3f3f3f3f /* 约 10.6 亿两数相加约 21 亿仍在 int 范围内 */ for (k 0; k n; k) for (i 0; i n; i) for (j 0; j n; j) if (weight[i][k] ! INF weight[k][j] ! INF /* 双保险 */ weight[i][j] weight[i][k] weight[k][j]) { weight[i][j] weight[i][k] weight[k][j]; path[i][j] k; }前面那个! INF判断是双保险。理论上 INF 取得够大就不会误判但加上这两个条件之后任何不可达的组合都会被挡在加法外面path表也不会被这些无效松弛污染。这一步在调试时特别有价值——如果发现path[i][j]被填了一个根本走不通的中间点八成就是漏了这个判断。顺便算一下这个规模下 INF 该取多少校园导航十个景点、九条边最长的一条边按现实里最远的两个点算撑死几百米。真实路径的上界是「边数 × 单边最大权」随便取个比它大十倍的数就够了没必要上到 INT_MAX。4.3 无向图只写了一遍边回程直接消失校园里的路都是双向的所以图是无向图邻接矩阵必须对称写了Edge[0][1] 20就必须补一句Edge[1][0] 20。原文里手写的那 28 条边是成对出现的一条边两行RowColWeight rcw[] { {0,1,20}, {1,0,20}, /* 食堂 - 男生宿舍 */ {0,2,30}, {2,0,30}, /* 食堂 - 操场 */ {5,8, 8}, {8,5, 8}, /* 草地 - 小门 */ /* ... 其余同理每条边必须写正反两次 */ };手写二十多条边的时候漏掉反向那条是家常便饭而且漏了不报错。表现就是第 2 章开头那个现象从 A 到 B 有路从 B 到 A 输出「没有通路」或者距离变成无穷大。如果打印函数没做 4.1 的判断屏幕上还会显示一个 1000看上去像条路更容易误判成算法问题。更省心的做法是不手写反向边构造图的时候自动补/* 构造无向图每条边写入两个方向避免手写遗漏 */ void CreatUndirected(AdjMGraph *G, DataType v[], int n, RowColWeight e[], int edgeCount) { int i; InitGraph(G, v, n); /* 顶点表 边矩阵初始化为 INF */ for (i 0; i edgeCount; i) { G-Edge[e[i].row][e[i].col] e[i].weight; G-Edge[e[i].col][e[i].row] e[i].weight; /* 反向自动补齐 */ } G-numOfEdge edgeCount; }这样rcw数组里每条边只写一行edgeCount从 28 降到 14出错概率直接减半。参数上e[]传的是「起点、终点、权值」三元组数组edgeCount是边的实际条数别再写成顶点数——这两个数混用是另一个高频翻车点传成 10 的话只建了十条边后面几条边对应的景点就成了孤岛。4.4 起点和终点相同时的距离与路径weight[i][i]初始化为 0这是邻接矩阵的标准初始化。但很多实现只把对角线之外的格子填成 INF对角线忘了置 0于是查「图书馆到图书馆」返回 1000 或者一个莫名其妙的数。初始化时记住两句话对角线是 0其余先是 INF有边的位置按边的权值覆盖。自查一行就够for (i 0; i n; i) if (G.Edge[i][i] ! 0) printf(顶点 %d 的自环初始化有问题\n, i);5. 避坑交报告前我必查的五个地方5.1 查一次景点菜单又弹一次点几下程序就退了现象输入 1 查完景点信息菜单又刷一遍连续查三五次之后程序无任何提示直接结束或者在某些编译器下报栈溢出。原因menu()里switch转到Information1()而Information1()末尾又调了一次menu()。每查一次就压一层新的栈帧永不返回等于用递归实现了一个主循环。景点数量不多时看不出问题连续操作几十次就可能把栈耗光。更隐蔽的是switch没有default分支输入 3 之类的越界选项时什么都不做直接落出函数整个调用链开始逐层返回看起来就像「点什么都没反应然后退出了」。解决菜单只写一层循环查询函数不许再调菜单void menu(void) { int n; for (;;) { /* 主循环永不递归 */ printf(\n1.景点信息查询 2.最短路径查询 0.退出\n请选择); if (scanf(%d, n) ! 1) break; /* 输入非数字跳出防死循环 */ if (n 0) break; switch (n) { case 1: Information1(); break; /* 查完自然返回循环 */ case 2: Path1(); break; default: printf(没有这个选项\n); } } }改造后的关键差别是Information1()和Path1()结尾不再调用menu()查完直接 returnfor(;;)负责回到菜单。scanf的返回值判一下防止用户输入字母导致n保持上一次的值、程序在同一个菜单上疯狂刷屏。5.2 输入景点名后下一个输入被自动跳过现象提示「请输入两个景点名」敲完第一个直接回车程序立刻报找不到第二个输入框根本没等。原因上一次读菜单选项用的是scanf(%d, n)它只吃掉了数字回车符\n还留在输入缓冲区里。紧接着的fgets或gets一上来就读到这个换行得到一个空串。解决数字和字符串的读取方式不要混着用。要么在%d后面加一个空格吸收空白scanf(%d , n)这种写法对交互式输入不友好会卡住等下一个字符不推荐要么统一改用fgets读整行再sscanf解析char line[64]; fgets(line, sizeof(line), stdin); if (sscanf(line, %d, n) ! 1) continue; /* 解析失败就重新显示菜单 */这样输入缓冲区每次都被整行读空绝不会留下残余字符。多花两行代码能省掉一整晚的「为什么第二个输入没反应」。5.3 换台电脑编译报「无法打开包括文件」现象自己机器上编译通过拷到同学电脑或者机房机器上第一行就报fatal error C1083: 无法打开包括文件: AdjMGraph.h。原因这个工程被拆成了school.cpp加AdjMGraph.h、AdjMGraphCreat.h、SeqList.h、Floyd.h、Operation.h、Inquiry.h一共七个文件。#include AdjMGraph.h用的是双引号编译器先在源文件所在目录找找不到再去系统目录找。换了目录之后如果只拷了.cpp没拷头文件或者头文件放进了子目录立刻报这个错。解决先把六个头文件和源文件放在同一级目录确认编译器的「工作目录」和源文件所在目录是一回事。如果非要分目录就在编译选项里显式加路径# GCC-I 指定头文件搜索目录 gcc school.cpp -I./include -o schoolVS 系列则在项目属性里找「C/C → 常规 → 附加包含目录」。另外还有一种假性报错头文件确实在同一目录但文件名大小写不一致Linux 下区分大小写、Windows 下不区分从 Windows 拷到 Linux 编译就会翻车。5.4 把景点数从 10 改到 50程序一跑就崩现象图小的时候一切正常把MaxVertices调大、景点加到几十个之后程序启动就异常退出或者跑着跑着报栈溢出。原因Floyd里的weight和path都是函数内部的局部数组int weight[MaxVertices][MaxVertices]这种二维数组是实打实占栈空间的。10×10×4 字节只有 400 字节无所谓但两个这样的数组、再把顶点数往上翻几倍几十 KB 的栈占用在默认栈大小下就很危险了。解决大数组不要放栈上挪到全局或者动态分配/* 放到文件作用域编译器分配在静态区不受栈大小限制 */ static int g_weight[MaxVertices][MaxVertices]; static int g_path[MaxVertices][MaxVertices]; void Path(AdjMGraph *G, int s, int t) { Floyd(G-Edge, G-vertices.size, g_weight, g_path); /* 传全局数组 */ printPath(g_path, s, t, G-vertices); }static表示只在本文件可见避免多个头文件重复定义同一个符号引发链接错误。代价是这两个数组不再可重入但对于单线程的控制台程序完全够用。5.5 报告里写的空间复杂度和代码对不上现象复杂度分析那一节写着「Floyd 算法时间复杂度 O(n³)空间复杂度 O(1)」答辩时被问一句「你的 weight 表和 path 表不算空间吗」就答不上来。原因O(1) 通常指算法除了输入之外不额外开辟随规模增长的存储。Floyd 里明摆着开了两张 n×n 的表那是 O(n²)写成 O(1) 是硬伤。真正 O(1) 的是单次松弛那一步。解决按实际代码重新写一遍。操作时间复杂度空间复杂度说明按名称查景点信息O(n)O(1)顺序表线性扫描除循环变量外无额外开销Floyd 预处理O(n³)O(n²)三重循环weight 与 path 各占 n×n查询一次最短路O(1)O(n)结论已预存只剩打印路径要栈最深 n 层把「预处理」和「单次查询」拆开写既准确又能体现出 Floyd 全源预处理的取舍建表贵一次之后每次查询都是常数时间。这一点在答辩时是个加分项比含糊地写一句 O(n³) 强很多。6. 快速定位三步分清是图错了、算法错了还是打印错了故障现象五花八门但落到这个系统上出问题的位置跑不出三层图的构建、Floyd 的松弛、路径的还原。乱序打印和距离算错看起来都是「路径不对」排查顺序却完全不同按下面三步走基本能一次定位。6.1 第一步把邻接矩阵打出来先确认图是对的这是最容易被跳过、也最省时间的一步。写个二十行的 dump 函数把矩阵原样输出/* 打印邻接矩阵INF 显示为 -1便于肉眼核对边的有无与对称性 */ void dumpMatrix(AdjMGraph *G) { int i, j; printf( ); for (i 0; i G-vertices.size; i) printf(%4d, i); printf(\n); for (i 0; i G-vertices.size; i) { printf(%3d: , i); for (j 0; j G-vertices.size; j) printf(%4d, G-Edge[i][j] INF ? -1 : G-Edge[i][j]); printf(\n); } }盯三件事第一对角线是不是全 0第二矩阵是不是沿对角线对称随便挑几个格子比一下Edge[5][8]和Edge[8][5]第三numOfEdge和你手写的边条数对不对得上。这一步花两分钟能挡掉后面一大半的误判。6.2 第二步用三个点的小图手算对照大图出错时把规模砍到三个点、两条边手算一遍最短距离再和程序输出比。三个点的图里Floyd 只有 27 次内层判断出不了花如果这时候结果都不对那一定是初始化或者松弛条件写错了不用再怀疑路径打印。症状先看哪张表典型结论距离明显偏大weightINF 太小被当成了正常距离或某条边的反向没补距离为负weightINF 取了 INT_MAX加法溢出距离对、路径缺节点path还原逻辑的游标改错了方向第 2 章距离对、路径多节点path漏判path -1重复打印了中转点查不到景点顶点表中文比对失败第 3 章换个方向就不可达邻接矩阵无向图只写了一半边4.36.3 第三步把打印逻辑单独拿出来测最后这步是我的习惯不去跑整个菜单而是手写一个固定的path表和一组起终点直接调打印函数。/* 不走 Floyd手工造一张 path 表单测打印函数 */ int testPath[MaxVertices][MaxVertices]; memset(testPath, -1, sizeof(testPath)); /* 全部置 -1即默认直达 */ testPath[0][4] 2; /* 0 到 4 经过 2 */ testPath[2][4] 3; /* 2 到 4 再经过 3 */ printPath(testPath, 0, 4, G.vertices); /* 期望0 - 2 - 3 - 4 */期望结果能手算输入完全确定只要输出不对问题百分之百在打印函数里跟 Floyd、跟图都没关系。这个办法的好处是把三层压缩成一层不用在几十个景点里瞎猜。从那以后我每次写这类带路径还原的程序都强制先跑这一组手写 path 表的单测绿了再接 Floyd省下来的时间远比写这几行多。希望帮到你。前面这套排查顺序和代码都是从校园导航系统那份课程设计里一点点抠出来的完整的头文件拆分结构、景点数据、28 条边的邻接矩阵和测试用例都在文档里需要照着对一遍的话直接拿它去比对自己的实现就行。本文还有配套的精品资源点击获取