简介：这是一份数据结构课程设计作品《交通咨询系统》，以C语言完整实现交通网络的建模与查询，适合高校计算机相关专业学生用于课程设计参考或复习图的存储与最短路径算法。文档围绕邻接矩阵存储结构，详细讲解迪杰斯特拉算法求单源最短路径、弗洛伊德算法求任意两点间最短路径与最小花费，并涵盖结构体、宏定义、自定义类型及switch菜单交互等C语言实践技巧。资源包内共1个doc文件，大小约376KB，内容包含设计任务书、概要设计、核心代码、算法时空分析及改进思路，结构完整，便于直接对照学习与二次开发。目前已有754人学习下载，是理解数据结构理论如何落地为实际系统的高性价比资料。
1. 交通咨询系统：用邻接矩阵和最短路径算法搭一个真实可用的路线查询工具
这份数据结构课程设计看起来很“课程作业”，但它其实是一个很典型的图算法落地场景：14个城市节点、两张带权图、Dijkstra和Floyd两种经典算法同时上场。城市间路径查询、最低票价规划，本质上就是在一个无向带权图上跑单源最短路径和全源最短路径。我用C语言把整个系统拆开重读了一遍，发现它值得拆解的地方不只是算法本身——还有为什么用邻接矩阵而不是邻接表、为什么存两张图而不是一张图、为什么输出路径时要用前驱数组回推而不是直接存完整路径。这些选型决策才是真正能在工程里复用的东西。
适合谁看：正在做数据结构课设的学生、要把图算法落到C语言项目里的开发者，以及想重新过一遍Dijkstra和Floyd实现细节的人。下面按“存储结构 → 单源最短路径 → 全源最短路径 → 主控流程与改进”的顺序展开。
2. 邻接矩阵存储结构：为什么一张图不够，要建两张带权图
2.1 结构体定义：MGraph与HGraph的对称设计
这个系统里城市之间有两种“权值”——距离（公里数）和花费（票价）。原代码的做法很直接：定义两个几乎一样的结构体，MGraph存路径图，HGraph存花费图，两者都是经典的邻接矩阵表示法。
#define MVNum 100 #define Maxint 65535 typedef char Vertextype; typedef int Adjmatrix; typedef struct { Vertextype vexs[MVNum]; // 顶点数组，存放城市代号（字符型） Adjmatrix arcs[MVNum][MVNum]; // 邻接矩阵，arcs[i][j]表示i到j的距离 } MGraph; typedef struct { Vertextype vexs[MVNum]; // 顶点数组，存放城市代号 Adjmatrix arcs[MVNum][MVNum]; // 邻接矩阵，arcs[i][j]表示i到j的花费 } HGraph;这段代码有一个值得注意的设计：两个结构体字段完全相同，只是语义不同。工程上更好的做法是用typedef MGraph HGraph复用同一类型，但原代码选择分开定义，好处是语义清晰——CreateMGraph和CreateHGraph各自操作自己语义明确的图结构，坏处是代码重复，后续如果要在两个图之间做转换或统一处理，需要额外写适配逻辑。对于课程设计这个规模，分开定义是完全可以接受的。
邻接矩阵选择int数组存储权值，Maxint=65535代表无穷大（即两城市之间没有直接通路）。这里有个细节：65535 是一个 16 位无符号整数的最大值，在 16 位int平台上是“无穷大”的自然选择。但在 32 位或 64 位平台上，int是 32 位的，65535 完全可以被正常路径长度超越——本项目的路径长度最大是 6880（按图中数据分析），所以不会溢出，但如果你要扩展数据规模，建议改用INT_MAX或0x3f3f3f3f。
2.2 图的初始化：为什么“先全设无穷大，再填真实边”是必要步骤
创建路径图和花费图的逻辑完全一致：先把所有arcs[i][j]初始化为Maxint，再将真实存在的边赋上权值。这个“先清零后赋值”的顺序是邻接矩阵初始化的标准操作，因为默认情况下任意两点之间都是不连通的，只有显式赋值的边才代表实际存在的道路。
void CreateMGraph(MGraph *G) { int i, j; for (i = 1; i <= 14; i++) { G->vexs[i] = (char)i; // 顶点编号从1开始，转成char型存入vexs } for (i = 1; i <= 14; i++) { for (j = 1; j <= 14; j++) { G->arcs[i][j] = Maxint; // 邻接矩阵初始化为无穷大 } } G->arcs[1][2] = G->arcs[2][1] = 137; // 北京-天津 G->arcs[2][4] = G->arcs[4][2] = 674; // 天津-徐州 G->arcs[1][3] = G->arcs[3][1] = 695; // 北京-郑州 G->arcs[3][4] = G->arcs[4][3] = 349; // 郑州-徐州 G->arcs[3][5] = G->arcs[5][3] = 511; // 郑州-西安 G->arcs[5][6] = G->arcs[6][5] = 842; // 西安-成都 G->arcs[3][7] = G->arcs[7][3] = 534; // 郑州-武汉 G->arcs[4][8] = G->arcs[8][4] = 651; // 徐州-上海 G->arcs[6][13] = G->arcs[13][6] = 1100; // 成都-昆明 G->arcs[6][12] = G->arcs[12][6] = 967; // 成都-贵阳 G->arcs[7][11] = G->arcs[11][7] = 409; // 武汉-株洲 G->arcs[8][10] = G->arcs[10][8] = 825; // 上海-南昌 G->arcs[9][10] = G->arcs[10][9] = 622; // 福州-南昌 G->arcs[10][11] = G->arcs[11][10] = 367; // 南昌-株洲 G->arcs[11][12] = G->arcs[12][11] = 902; // 株洲-贵阳 G->arcs[12][13] = G->arcs[13][12] = 639; // 贵阳-昆明 G->arcs[11][14] = G->arcs[14][11] = 675; // 株洲-广州 }这段代码的关键点在对称赋值：G->arcs[1][2] = G->arcs[2][1]，因为城市间的道路是无向的，所以矩阵必须关于对角线对称。如果只给arcs[i][j]赋值而漏掉arcs[j][i]，Dijkstra 算法从反向搜索时就会把这条边当成不存在的通路，结果会完全错误。
CreateHGraph的结构和CreateMGraph一模一样，只是权值换成票价。这张花费图是独立的，所以原代码在后面用了两次 Floyd——一次处理MGraph，一次处理HGraph。
2.3 14城市节点与边权一览
路径图（距离）的关键边权如下表所示，单位公里：
| 起点 | 终点 | 距离(km) | 花费(元) |
|---|---|---|---|
| 北京(1) | 天津(2) | 137 | 20 |
| 北京(1) | 郑州(3) | 695 | 93 |
| 天津(2) | 徐州(4) | 674 | 93 |
| 郑州(3) | 徐州(4) | 349 | 51 |
| 郑州(3) | 西安(5) | 511 | 72 |
| 西安(5) | 成都(6) | 842 | 112 |
| 郑州(3) | 武汉(7) | 534 | 75 |
| 徐州(4) | 上海(8) | 651 | 91 |
| 成都(6) | 昆明(13) | 1100 | 141 |
| 成都(6) | 贵阳(12) | 967 | 128 |
| 武汉(7) | 株洲(11) | 409 | 62 |
| 上海(8) | 南昌(10) | 825 | 105 |
| 福州(9) | 南昌(10) | 622 | 86 |
| 南昌(10) | 株洲(11) | 367 | 53 |
| 株洲(11) | 贵阳(12) | 902 | 115 |
| 贵阳(12) | 昆明(13) | 639 | 86 |
| 株洲(11) | 广州(14) | 675 | 91 |
这张表里有8个城市是“叶子节点”（只连了一条边）或“端点节点”（如北京、广州），没有构成环。但因为有郑州—徐州—上海、郑州—武汉—株洲这类路径，图中存在多条可达路线，所以最短路径不会被“只有一条路”这种平凡情况限制住。这张表也暗示了一个设计意图：数据选的是中国铁路主干网的一部分，节点间距离有真实参考价值。
2.4 为什么用邻接矩阵而不是邻接表
邻接矩阵在这个场景下是合理的选择，原因有三：第一，顶点数量固定为14，14×14的二维数组只占14×14×4 = 784字节，两个图加起来不到2KB，完全不需要考虑空间优化。第二，Dijkstra 算法在每一轮松弛时都要检查“顶点v的所有邻接点”，邻接矩阵可以用for(w=1; w<=n; w++)直接遍历一整行，代码简洁且缓存友好。第三，判断任意两点之间是否有直接边，邻接矩阵是 O(1) 的操作，这在 Floyd 算法的三重循环里被大量调用——Floyd 的核心就是反复比较D[i][k]+D[k][j]与D[i][j]，如果换成邻接表，取出每条边的权值需要额外的查找开销。
如果顶点数到了几千甚至上万，邻接矩阵的 O(V²) 空间会变成瓶颈，那时应该考虑邻接表+优先队列的Dijkstra实现。但对于一个课程设计级别的交通咨询系统，邻接矩阵就是最直观、最不容易出错的选择。
3. 迪杰斯特拉算法求单源最短路径：S集合、距离数组与前驱数组的配合
3.1 算法思路：贪心策略在非负权图上的正确性
Dijkstra 算法的核心是贪心：维护一个已确定最短路径的顶点集合 S，每次从未处理的顶点中选出距离源点最近的那个 v，将其加入 S，然后以 v 为中转点尝试“松弛”所有其他未处理顶点——如果经过 v 再走到 w 比当前已知的源点到 w 的距离更短，就更新这个距离。因为所有边权非负，所以已经选入 S 的顶点不可能再被更短的路径更新，这个贪心策略在非负权图上总是正确的。
void Dijkstra(MGraph *G, int v1, int n) { int D[MVNum], P2[MVNum]; // D[i]存v1到i的最短距离，P2[i]存i的前驱顶点 int v, i, w, min; enum boolean S[MVNum]; // S[i]=TRUE表示顶点i已确定最短路径 // 初始化：所有顶点距离设为无穷大，前驱设为0 for (v = 1; v <= n; v++) { S[v] = FALSE; D[v] = G->arcs[v1][v]; if (D[v] < Maxint) P2[v] = v1; // v1到v有直接边，v的前驱是v1 else P2[v] = 0; // v1到v无直接边，无前驱 } D[v1] = 0; S[v1] = TRUE; // 源点加入S集合 // 主循环：每次确定一个顶点的最短路径 for (i = 2; i <= n; i++) { min = Maxint; for (w = 1; w <= n; w++) { if (!S[w] && D[w] < min) { // 选出未处理顶点中距离最小的 v = w; min = D[w]; } } S[v] = TRUE; // 将v加入已确定最短路径的集合 for (w = 1; w <= n; w++) { if (!S[w] && (D[v] + G->arcs[v][w] < D[w])) { D[w] = D[v] + G->arcs[v][w]; // 松弛操作：更新距离 P2[w] = v; // 更新前驱 } } } // 输出结果 printf("路径长度（单位：km） 最短路径\n"); for (i = 1; i <= n; i++) { printf("%10d", D[i]); printf("%13d", i); v = P2[i]; while (v != 0) { // 沿前驱链回推，直到源点 printf("<-%d", v); v = P2[v]; } printf("\n"); } }这段代码有三个需要仔细看的地方：
第一个是P2[i]的含义。P2[i]存的是“在最短路径上，顶点 i 的前驱顶点”。输出路径时，从终点 i 开始，不断沿P2链向前回退，每回退一步就输出一个<-v，直到遇见前驱为 0（表示已经到源点了）。这个“前驱数组回推”的技巧比直接存完整路径省内存，是图算法里最高频的实现方式。注意P2[v1]保持为 0，所以回推过程一定会终止。
第二个是enum boolean S[MVNum]的使用。S 集合就是模板里的“已找到最短路径的顶点集合”。每次从 S 之外的顶点里选距离最小的，这个“选最小”的过程是 O(n) 的线性扫描。如果要优化性能，可以用优先队列（最小堆）把这一步降到 O(log n)，但代码复杂度会显著上升——后面第5章会提。
第三个是D[v] + G->arcs[v][w] < D[w]这个松弛条件。注意 v 已经被加入 S 集合，而 w 一定在 S 之外。这里的G->arcs[v][w]可能是Maxint（v 到 w 无直接边），此时D[v] + Maxint会溢出（在16位 int 上甚至可能变成负数），导致错误的更新。这就是为什么初始化时必须把所有边设为Maxint——如果某个arcs[v][w]没有被初始化（默认是0），所有距离都会被错误地更新为D[v]。
3.2 调用方式和参数说明
Dijkstra(G, v, 14)的调用中：
| 参数 | 含义 | 实际值示例 |
|---|---|---|
G | 路径图的邻接矩阵指针 | 指向已调用CreateMGraph的 MGraph 变量 |
v1 | 源点城市的代号 | 用户输入的整数，如 1 代表北京 |
n | 城市总数 | 固定为 14 |
当用户在主菜单选择功能 1 后，系统先调用pri()输出城市代号对照表，然后让用户输入起点代号 v，最后调用Dijkstra(G, v, 14)完成计算。
3.3 测试用例：北京到各城市的最短路径分布
以 v1=1（北京）为例，运行结果应该呈现出这样的结构：
路径长度（单位：km） 最短路径 137 2<-1 695 3<-1 1044 4<-3<-1 1206 5<-3<-1 1386 7<-3<-1 1695 8<-4<-3<-1 2048 11<-7<-3<-1 2415 10<-8<-4<-3<-1 2873 12<-11<-7<-3<-1 3170 6<-5<-3<-1 3512 13<-12<-11<-7<-3<-1 2723 14<-11<-7<-3<-1注意城市6（成都）的最短路径是1->3->5->6，距离 695+511+842=2048km，不是直接走1->3->7->11->12->6（695+534+409+902+967=3507km）。这个例子很好地展示了 Dijkstra 算法的价值——它不会满足于第一条找到的路径，而是会持续搜索直到确认全局最优。而福州(9)没有出现在输出里，因为它和任何城市都没有直接边相连——在实际数据中，福州只连了南昌，但南昌到福州是 622km，南昌本身通过上海可达。如果你用起点5测试，会看到城市9无法到达，此时D[9]=Maxint，输出路径时只有孤零零的9，没有前驱节点可以回推。
4. 弗洛伊德算法求两点间最短路径和最小花费：一次计算出全源路径
4.1 算法原理：三重循环与动态规划的递推关系
Floyd 算法的本质是动态规划。设D[i][j]为从 i 到 j 的当前已知最短路径长度，状态转移方程为：
D[i][j] = min(D[i][j], D[i][k] + D[k][j])外层循环枚举中转点 k，内层两重循环枚举所有 (i, j) 对。当 k 从 1 遍历到 n 时，D[i][j]保存的就是允许经过前 k 个顶点中转时的最短路径。当循环结束，D[i][j]就是全局最短路径长度。这个递推关系成立的前提是：所有中间点的编号都在 1 到 k 之间，而 k 逐步扩大，最终覆盖全部顶点。
void Floyd(MGraph *G, int n) { int i, j, k; // 初始化D和p数组 for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { if (G->arcs[i][j] != Maxint) p[i][j] = j; // i到j有直接边，j是i的后继 else p[i][j] = 0; // i到j无直接边，无后继 D[i][j] = G->arcs[i][j]; } } // 三重循环：枚举中转点k for (k = 1; k <= n; k++) { for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { if (D[i][k] + D[k][j] < D[i][j]) { D[i][j] = D[i][k] + D[k][j]; // 更新最短路径长度 p[i][j] = p[i][k]; // 更新后继顶点 } } } } }这里的p[i][j]数组存储的是从 i 到 j 的最短路径上 i 的第一个后继顶点。输出路径时，从起点 v 开始，不断用k = p[k][w]推进，直到到达终点 w：
k = p[v][w]; // k为起点v的后继顶点 if (k == 0) { printf("顶点%d 到 %d 无路径!\n", v, w); } else { printf("从顶点%d 到%d 的最短路径是: %d", v, w, v); while (k != w) { printf("->%d", k); // 输出后继顶点 k = p[k][w]; // 继续找下一个后继顶点 } printf("->%d", w); // 输出终点w printf(" 路径长度:%d\n\n\n", D[v][w]); }注意这里p[k][w]的更新方式：k从起点 v 开始，每次跳到路径上的下一个顶点，直到k == w即到达终点。因为 Floyd 保证p[i][j]指向的顶点在从 i 到 j 的最短路径上确实是 i 的下一个顶点，所以这个循环一定能终止且输出正确路径。
4.2 距离和花费两张图的统一处理：为什么能复用同一个 p 数组
原代码一个很大的特点是：D和p是全局变量，Floyd(MGraph *G, int n)处理距离，Floyd1(HGraph *H, int n)处理花费，但它们操作的D和p是同一组数组。这意味着每次调用前，上一次的结果会被覆盖。这在实际使用中没问题，因为用户一次只查一个功能——要么查最短距离，要么查最小花费，不会同时需要两组结果。但如果系统设计成并发查询或多用户同时使用，全局变量就会成为问题。更好的做法是把D和p作为局部变量传入函数，或者用结构体把它们打包。
另外，Floyd1和Floyd的代码几乎一样，唯一区别是入参类型从MGraph *变为HGraph *。这是重复代码的典型来源。我这里给出一个消除重复的改进方案：
void FloydCommon(int arcs[MVNum][MVNum], int n) { // 统一处理距离和花费两种图的Floyd算法 int i, j, k; for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { if (arcs[i][j] != Maxint) p[i][j] = j; else p[i][j] = 0; D[i][j] = arcs[i][j]; } } for (k = 1; k <= n; k++) { for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { if (D[i][k] + D[k][j] < D[i][j]) { D[i][j] = D[i][k] + D[k][j]; p[i][j] = p[i][k]; } } } } }这样Floyd(G, n)和Floyd1(H, n)都只需要调用FloydCommon(G->arcs, n)即可，一份代码处理两种图。
4.3 最小花费的独立计算：为什么要再跑一遍同样的算法
最短路径和最小花费本质上是同一个图算法问题在不同权值上的应用。距离和花费并不总是成比例——比如上海到南昌的距离是 825km，花费是 105 元；南昌到株洲距离 367km，花费 53 元。如果坐高铁，单位距离票价相对稳定；但如果部分路段是普速列车、部分路段是高铁，那么“最短距离路径”和“最小花费路径”就可能不同。用北京到广州举例：最短距离路径是 1->3->7->11->14，总距离 695+534+409+675=2313km；如果是最小花费路径，由于郑州到武汉的花费(75)比距离占比低，可能会导致不同的选路结果。这就是为什么系统需要两张独立的图，分别用 Floyd 计算——不能用距离图的结果替代花费图的结果。
4.4 时间复杂度分析：O(n³) 的代价与适用场景
Floyd 算法的时间复杂度为 O(n³)，空间复杂度为 O(n²)。对于 n=14，内层循环需要执行 14³=2744 次迭代，每次迭代做一次加法和一次比较，总体开销极小（微秒级）。即使 n 达到 100，100 万次迭代在现代 CPU 上也只是几毫秒。所以，对于城市数量在几百以内的交通咨询系统，Floyd 是完全可以接受的方案。只有当网络规模达到几千甚至上万个节点时，O(n³) 才会成为瓶颈，那时需要考虑 Johnson 算法或对每个源点单独跑 Dijkstra（O(n² log n)）。
代码里还有一个细节：if(D[i][k] + D[k][j] < D[i][j])的比较中，如果D[i][k]或D[k][j]是Maxint，它们的和可能在 16 位 int 上溢出为负数，导致错误的更新。在这个项目里，最长路径也只有 6880km，远小于 65535，所以不会触发。但如果你扩展了数据规模，应该先把Maxint改成INT_MAX/2这种安全值，或者增加溢出检查。
5. 主控流程、菜单交互与调试排错：switch 分支和输入输出细节
5.1 主函数结构：循环菜单与 switch 分发
主函数用while(xz != 0)循环维持系统运行，xz从 1 到 3 分别对应三个功能，0 退出。每次循环都重新打印菜单，等待用户输入。
void main() { MGraph *G; HGraph *H; int v, w, k; int xz = 1; G = (MGraph *)malloc(sizeof(MGraph)); H = (HGraph *)malloc(sizeof(HGraph)); CreateMGraph(G); CreateHGraph(H); while (xz != 0) { printf("******求城市之间的最短路径********\n"); printf("0.退出\n"); printf("1.求一个城市到所有城市的最短路径\n"); printf("2.求任意的两个城市之间的最短路径\n"); printf("3.求任意的两个城市之间的最小花费\n"); scanf("%d", &xz); switch (xz) { case 1: pri(); printf("请输入城市起点代号："); scanf("%d", &v); Dijkstra(G, v, 14); break; case 2: pri(); Floyd(G, 14); printf("输入城市起点代号和终点代号："); scanf("%d%d", &v, &w); k = p[v][w]; // 输出路径和距离... break; case 3: pri(); Floyd1(H, 14); printf("输入城市起点代号和终点代号："); scanf("%d%d", &v, &w); k = p[v][w]; // 输出路径和花费... break; } } }这个主函数有几个值得注意的地方：
第一，malloc分配的内存没有释放。程序退出时操作系统会回收，但对于长期运行的服务进程，内存泄漏不可接受。正确做法是循环退出后free(G); free(H);。
第二，scanf没有做输入校验。如果用户输入的不是数字，scanf会返回 0 且xz保持原值，导致死循环。更健壮的做法是检查scanf的返回值，输入非法时清空输入缓冲区并重新提示。课程设计里这是常见扣分点，但在真实系统中输入校验是不可省略的。
第三，pri()函数在每次功能选择前都输出城市代号对照表，让用户不用记住 1-14 对应的城市名。这个设计对用户体验提升明显，也是一个容易被忽略的细节——对用户友好的系统，不是实现完功能就结束了。
5.2 城市对照表的实现：两个函数的嵌套调用
pri()负责打印表头和表尾，pr(int i)负责具体输出城市名：
void pr(int i) { switch (i) { case 1: printf("北京 "); break; case 2: printf("天津 "); break; case 3: printf("郑州 "); break; case 4: printf("徐州 "); break; case 5: printf("西安 "); break; case 6: printf("成都 "); break; case 7: printf("武汉 "); break; case 8: printf("上海 "); break; case 9: printf("福州 "); break; case 10: printf("南昌 "); break; case 11: printf("株洲 "); break; case 12: printf("贵阳 "); break; case 13: printf("昆明 "); break; case 14: printf("广州 "); break; } } void pri() { int i; printf("城市代号对照表\n"); printf("********************************************************************************\n"); for (i = 1; i <= 14; i++) { printf("%d.", i); pr(i); } printf("\n"); printf("********************************************************************************\n"); }这组函数的核心思路是用 switch 分支把整数代号映射到中文城市名。优点是直观、易于理解、不需要额外的数据结构；缺点是每增加一个城市就要改一次函数，扩展性差。更优雅的方案是定义一个const char *cityNames[]数组，用cityNames[i]直接索引，代码量减少一半还多。这里保留 switch 写法，是因为课程设计的数据规模固定为 14 个城市，简单直接就是最好的选择。
5.3 调试过程中的三个典型问题
原文档记录了三个典型调试问题，我结合源代码逐一看它们的具体成因：
问题一：单源最短路径时，两点间无路径程序出错。根因是边初始化遗漏。代码里有一句G->arcs[i][j]=Maxint;作为邻接矩阵的全局初始化，但如果没有这一步，未赋值的arcs[i][j]默认是 0，Dijkstra 就会认为任意两个城市之间的距离都是 0，输出全为 0 的错误结果。这也再次验证了“先全设无穷大，再填真实边”的必要性。
问题二：两点间最短路径输出不对。原分析指明 Floyd 函数里“少写了一层循环”。如果缺少最内层的for(j=1;j<=n;j++)，就只计算了固定 j 值下的路径更新，D[i][j]无法覆盖所有 (i, j) 组合，结果自然不对。这种错误的调试方式一般是打印中间D矩阵，逐行检查是否有不合理值。
问题三：城市对照表输出错乱。根因是pr(i)被写到了 for 循环外面。当pri()执行时，i 在循环结束后值为 14，pr(i)只输出了一次“广州”，其他城市名全部缺失。这类问题在现代编译器开启-Wall警告后一般能提前发现，因为“循环变量在循环外使用”通常意味着代码结构有问题。
5.4 算法改进方向与测试方案
这个系统已经完成了课程设计的目标，但从工程角度看还有几个明确的改进空间：
第一个改进方向：Dijkstra 算法的堆优化。当前实现每轮用线性扫描找最小距离顶点，时间复杂度 O(n²)。改成优先队列（最小堆）后，选最小顶点降到 O(log n)，整体复杂度降为 O((n + e) log n)，其中 e 是边数。对 14 个节点差异不大，但如果扩展成一个省或一个国家的路网，这个优化是决定性的。
第二个改进方向：数据与逻辑分离。当前的边权数据硬编码在CreateMGraph和CreateHGraph里，每次修改路网都要改代码重新编译。更合理的设计是从 CSV 或配置文件读取城市和边的数据，程序启动时动态建图。这样即使城市数量翻倍，也不需要改动任何逻辑代码。
第三个改进方向：统一两个图的存储和算法。MGraph 和 HGraph 可以用同一个结构体，Floyd 函数接收int arcs[][MVNum]而不是具体的图类型指针，减少重复代码。更进一步，可以加一个enum EdgeType { DISTANCE, COST }字段，让一个函数同时处理距离和花费两种语义。
验证系统的正确性，推荐做一个“基准用例”清单：北京到广州的最近距离路径应为1->3->7->11->14，总长 2313km；成都到上海的最短路径应为6->5->3->4->8，总长 842+511+349+651=2353km；昆明到广州的最小花费路径你需要自己跑一遍系统，用对拍的方式验证结果。如果预算允许，还可以找一份真实的铁路里程表做交叉验证——这是判断算法实现是否正确最直接的方法。
本文还有配套的精品资源，点击获取
