简介面向数据结构课程设计学习者及算法爱好者这份资源提供了一套完整的Dijkstra算法求最短路径课程设计报告doc格式。报告按问题分析与任务定义、数据结构选择与概要设计、详细设计与编码、上机调试四大章节组织条理清晰内容涵盖带权有向图的存储与显示、邻接矩阵的构建、递归函数的应用以及Dijkstra算法求解单源最短路径的核心步骤并配有测试用例、调试错误记录、时间与空间性能分析及学习心得体会。报告中还细致说明了从建图、显示邻接矩阵到递归输出路径的完整流程针对调试中容易遇到的错误给出了处理办法能帮助读者避开典型实现陷阱。Dijkstra算法在交通网络、计算机网络等单源最短路场景应用广泛结合完整报告可加深对经典算法的理解。资源为单个doc文档体积仅182KB轻量易读适合作为数据结构课程设计参考模板、算法复习提纲或报告撰写范例。目前已有321人学习下载尤其适合初次接触图论最短路径、需要借鉴完整报告结构与编码思路的学习者。1. 一份能跑通全流程的 Dijkstra 算法课设从邻接矩阵到最短路径输出数据结构课程设计里绕不开的一道题就是用 Dijkstra 算法求最短路径。中南大学这份第 9 题课设报告用 C 语言在邻接矩阵上实现了从建图、显示矩阵到输出单源最短路径的完整闭环代码可以直接编译跑通。它适合正在写课程设计的人当模板也适合考研数据结构复习到图的部分时拿来对照实验。报告的亮点不在算法本身而在路径如何用前驱数组递归恢复以及矩阵显示、输入格式这些问题在真实调试里如何暴露出来。下面把选型理由、代码细节和报告里没写透的坑一次讲清。2. 存储选型与 Dijkstra 原理邻接矩阵的优势和贪心三步2.1 图的存储选型为什么最终选了邻接矩阵图的结构比线性表和树复杂任意两个顶点之间都可能存在关系不存在严格的前后顺序所以不能像线性表那样用简单数组直接存储全部关系如果采用链表各顶点度数差异可能很大按最大度数设计链域会浪费大量存储单元按每个顶点设计不同结点又会给操作带来很大困难。最终选择邻接矩阵的核心理由有两个第一判断两个顶点是否直接相连只需要查一个数组元素时间复杂度 O(1)这对 Dijkstra 主循环里的松弛判断非常友好第二求某个顶点的度很方便有向图里数行是出度、数列是入度。代价在报告里也写得很明白统计边数必须遍历整个二维数组时间复杂度 O(n²)顶点很多而边很少的稀疏图非常不合算。三种常见存储结构在这道题里的对比存储结构判断两点是否相连求顶点度空间复杂度适合场景直接数组边表遍历所有边遍历所有边O(e)极稀疏、边数少的图邻接表遍历顶点链表遍历链表入度需逆邻接表O(ne)稀疏图邻接矩阵O(1) 查 arcs[i][j].adj数一行或一列O(n²)稠密图、实现简单报告选的邻接矩阵在数据规模 25 个顶点以内时没有任何性能负担而代码复杂度远低于邻接表这是课程设计场景下的合理取舍。如果你在王道数据结构或者严蔚敏教材里看到邻接矩阵适合稠密图的结论这道题就是最好的印证。2.2 Dijkstra 算法为什么能用贪心初始化、选最小、松弛Dijkstra 算法的基本思想在报告里概括为按路径长度递增的次序逐步产生源点到其他各顶点的最短路径。它维护一个顶点集合 S初始时 S 只包含源点 V0每轮从 V-S 中选出当前 distance 最小的顶点 Vj 加入 S再用 Vj 去松弛其余不在 S 中的顶点。这里的贪心成立有一个大前提边的权值必须非负。因为 Vj 一旦被选入 S它的 D[j] 就被当作最终最短路径长度定案了后续不可能再出现一条经过其他未选顶点的路径比它更短。如果存在负权边可能出现绕一圈反而更小的情况Dijkstra 就会给出错误结果这时应该改用 Bellman-Ford 或 SPFA。S {V0} distance[i] cost[V0][i] // 源点到各顶点的直接权值 while S 未包含全部顶点: 在 V-S 中找 distance[j] 最小的顶点 Vj S S ∪ {Vj} for 每个 Vi ∈ V-S: if distance[j] cost[j][i] distance[i]: distance[i] distance[j] cost[j][i]伪代码里三个变量的含义distance[i] 是源点 V0 到 Vi 的当前最短路径长度cost[j][i] 是边 Vj, Vi 的权值S 是已确定最短路径的顶点集合。每一次松弛成功的含义是找到了从源点经 Vj 到 Vi 的更短通道。注意 distance[i] 在 Vi 入 S 之前都只是上界只有入 S 那一刻才成为终值。3. 带权有向图建图实现ArcCell 结构体、LocateVex 与输入陷阱3.1 类型定义为什么邻接矩阵元素是结构体而不是 int报告把邻接矩阵的元素定义成结构体 ArcCell而不是直接用 int 二维数组。这层抽象的价值在于ArcCell 的 adj 字段保存权值info 指针可以挂接每条弧的附加信息比如路段长度、通行时间、费用等。课设里 info 始终置 NULL但结构上保留了这个扩展位后期加字段不用改所有函数签名。常量 MAX_VERTEX_NUM 是 25INFINITY 是 3000。选 3000 而不是 int 最大值不是随手写的后续松弛判断里有 min G-arcs[i][n].adj 这个加法如果 INFINITY 取 INT_MAX加一个正权值会直接溢出成负数比较逻辑全部失效。3000 大于任何正常权值累加结果25 个顶点、个位数权值累加也不超过几百又不会溢出是课程设计里的安全大数。#define MAX_VERTEX_NUM 25 #define INFINITY 3000 typedef char VertexType; // 顶点字符如 A typedef int VRType; // 顶点关系类型即权值 typedef int InfoType; // 弧相关信息类型 typedef struct ArcCell { VRType adj; // 两点间权值INFINITY 表示不可达 InfoType *info; // 弧相关信息的指针课设中置 NULL } ArcCell; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; // 顶点数组 ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int vexnum, arcnum; // 当前顶点数和弧数 } MGrph;vexs 数组按下标 0 到 n-1 存储顶点字符arcs[i][j].adj 存储从顶点 i 到顶点 j 的权值。有向图的特性体现在这里arcs[i][j] 和 arcs[j][i] 是两个独立元素可以一个有权值、另一个是 INFINITY分别表示两条方向相反的弧。3.2 顶点定位与建图函数scanf 格式串是第一个坑LocateVex 通过遍历 vexs 数组把顶点字符转换成数组下标。原始代码在找不到时返回的是最后一个 j 值而不是 -1这是一个隐患。正常输入不会触发一旦用户输入了图里不存在的顶点程序会静默写错位置。建议改成查到即返回、查不到返回 -1。Creat_YG 的建图流程分四步读入顶点数和弧数读入每个顶点字符把邻接矩阵全部初始化为 INFINITY按三元组 起点,终点,权值 逐条填边。int LocateVex(MGrph *G, VertexType v) { int b; for (b 0; b G-vexnum; b) if (G-vexs[b] v) return b; // 找到立即返回下标 return -1; // 找不到返回 -1供调用方判断 } void Creat_YG(MGrph *G) { int i, j, k, n; VertexType v1, v2; printf(请输入顶点个数和弧数如3,3:); scanf(%d,%d, G-vexnum, G-arcnum); for (i 0; i G-vexnum; i) { printf(请输入图的第%d个顶点:, i 1); while (getchar() ! \n); // 清掉上一行的回车避免被 %c 读到 scanf(%c, G-vexs[i]); } for (i 0; i G-vexnum; i) for (j 0; j G-vexnum; j) { G-arcs[i][j].adj INFINITY; G-arcs[i][j].info NULL; } for (k 0; k G-arcnum; k) { printf(请输入边的起点、终点、权值如A,B,5:); while (getchar() ! \n); scanf(%c,%c,%d, v1, v2, n); i LocateVex(G, v1); j LocateVex(G, v2); G-arcs[i][j].adj n; // 有向图只填 arcs[i][j] G-arcs[i][j].info NULL; } }原始代码里用的是 fflush(stdin)这在 Windows 的很多编译器下能工作但标准 C 并没有定义 fflush(stdin) 的行为换到 Linux 的 gcc 环境就不确定。我替换成 while (getchar() ! \n)循环读到换行符为止把残留字符消费掉这是可移植的清空缓冲写法。提示在标准 C 中 fflush(stdin) 是未定义行为跨编译器时建议用 while (getchar() ! \n) 清空输入缓冲。scanf 的格式串 %c,%c,%d 要求输入严格带逗号A,B,5 才对。注意 %c 不会跳过空白字符如果用户写 A,B, 5 或 A B 5v1 或 v2 就会读进空格或逗号后续 LocateVex 找不到顶点建图就乱了。报告在调试部分记录了这个现象当输入格式不符合程序要求时会出现循环原因就在这里。3.3 邻接矩阵显示把 3000 打出来有利于调试juzhen 函数用两重循环输出矩阵第一行是列顶点名第一列是行顶点名中间每个格子里输出权值没有弧的两点输出 3000。void juzhen(MGrph *G) { int i, j, k; printf(邻接矩阵显示\n); printf(\t); for (i 0; i G-vexnum; i) printf(\t%5c, G-vexs[i]); for (j 0; j G-vexnum; j) { printf(\n\n); printf(\t%5c, G-vexs[j]); for (k 0; k G-vexnum; k) { if (G-arcs[j][k].adj INFINITY) printf(\t%5d, G-arcs[j][k].adj); else printf(\t 3000); } } printf(\n); }输出格式里 %5c 和 %5d 是让每个单元格占 5 个字符宽度矩阵按列对齐肉眼检查时能快速看出哪些顶点之间有弧。把 3000 直接打印出来对调试友好但对最终用户来说3000 会被误认为是一条权值 3000 的边。更严谨的处理方式是输出∞或直接留空这个在第 5 章结合不可达判断一起讨论。4. Dijkstra 核心实现final / path / D 三个数组与递归路径恢复4.1 三个一维数组如何替代教材里的 S 集合教材里讲 Dijkstra 通常用集合 S、distance 数组、path 数组三个概念。报告用 final[30]、D[30]、path[30] 三个一维数组实现final 就是 S 集合的布尔化表示D 就是 distancepath 记录前驱。这种写法避免了手动维护集合结构全部用数组下标操作贴合 C 语言课设的实现难度。数组作用初始化更新时机final[i]标记顶点 i 是否已入集合 S全 0源点置 1每轮选出最小值顶点后置 1D[i]源点到顶点 i 的当前最短路径长度源点到各点的直接权值松弛成功时path[i]顶点 i 的前驱顶点下标全部置为源点下标松弛成功时三个数组的关系final 是判据决定哪些顶点不参与后续比较D 是结果记录当前最优长度path 是轨迹保证最终能还原整条路径。path 初始化为源点下标意味着初始假设所有顶点都直接从源点到达随着松弛进行path[i] 会指向真正让路径变短的中间顶点。4.2 主循环找最小值再松弛的完整代码void ShortestPath(MGrph *G, int w) { int i, k, m, n, min; int final[30], path[30], D[30]; for (i 0; i G-vexnum; i) { path[i] w; // 前驱先指向源点 final[i] 0; // 全部未入集合 D[i] G-arcs[w][i].adj; // 初始距离为源点到 i 的直接权值 } D[w] 0; final[w] 1; // 源点入集合最短路径长度为 0 path[w] -100; // 源点没有前驱用 -100 做哨兵 for (m 1; m G-vexnum; m) { min INFINITY; for (k 0; k G-vexnum; k) if (!final[k] D[k] min) { i k; // i 记录本轮 D 最小的顶点 min D[k]; } final[i] 1; // 该顶点最短路径定案入集合 S for (n 0; n G-vexnum; n) if (!final[n] (min G-arcs[i][n].adj) D[n]) { D[n] min G-arcs[i][n].adj; // 松弛成功更新长度 path[n] i; // 记录前驱 } } }外层循环执行 n-1 轮因为源点已经入集合剩下 n-1 个顶点每轮定案一个。内层第一个 for 在未入集合的顶点里找 D 最小min 记录长度、i 记录下标找到后 final[i] 置 1。第二个 for 做松弛min G-arcs[i][n].adj 表示源点经 i 到 n 的新路径长度如果比当前 D[n] 小就更新 D[n] 和 path[n]。两个边界细节需要留意。第一个如果 i 到 n 没有弧arcs[i][n].adj 是 INFINITYmin INFINITY 大于任何有限值不会误更新。第二个如果源点本身到某顶点不可达D[n] 一直是 INFINITY但 3000 仍会被当成当前最小值选入集合最终打印最短路径长度为 3000这个问题在第 5 章专门解决。4.3 递归路径恢复前驱数组输出完整路径的原理path 数组每个顶点只存一个前驱下标输出时从终点开始一路回溯到源点正好是一条完整的反序路径。Short 函数用递归实现回溯先打印前驱的前驱再打印当前前驱从递归回退顺序看就是从源点到终点的正序。void Short(MGrph *G, int path[], int i, int w) { int k path[i]; if (k ! w) Short(G, path, k, w); // 递归先打印前驱之前的部分 printf(%c,, G-vexs[k]); // 再打印当前前驱顶点 }调用时主函数里这样组合Short(G, path, m, w); // 打印到达终点 m 之前的所有中间顶点 printf(%c\n, G-vexs[m]); // 补打终点本身递归终止条件是 k w也就是前驱正好是源点。递归回退时从源点开始逐个打印自然形成 A,C,B 这样的正序路径。以顶点 B 为例假设 path[B] 存的是 C 的下标path[C] 存的是 A 的下标Short 先递归到 CC 的前驱是 A 等于 w于是先打印 A回退打印 C主函数再打印 B结果就是 A,C,B。报告在调试体会里写了一句无法具体记录经过的顶点数只能记录源点、终点前一顶点以及终点这实际上是对 path 数组的误判。path 数组天然支持从终点一路回溯到源点记录经过哪些顶点和经过几个顶点都可以在输出时顺带统计并不需要换成二维数组。5. 上机调试的坑与复杂度分析输入格式、不可达误判和 O(n²)5.1 输入格式问题的连锁反应报告第四章用了很大篇幅描述调试过程第一个问题就是输入格式。程序对格式的敏感来自 scanf(%c,%c,%d)它要求边信息严格写成字母、逗号、字母、逗号、数字。一旦用户输入 A B 5%c 会把 B 前面的空格读给 v2导致找不到顶点程序进入错误分支。课程设计里允许这种严格格式因为题目本身规定了输入规格。但真实交互中我一般会加一个校验循环让输入错误可以直接重来for (k 0; k G-arcnum; k) { printf(请输入边的起点、终点、权值如A,B,5:); while (getchar() ! \n); while (scanf(%c,%c,%d, v1, v2, n) ! 3 || LocateVex(G, v1) -1 || LocateVex(G, v2) -1) { while (getchar() ! \n); // 清掉这次错误输入 printf(格式错误请按 起点,终点,权值 重输:); } i LocateVex(G, v1); j LocateVex(G, v2); G-arcs[i][j].adj n; }scanf 返回值为 3 才表示三个变量都成功读取LocateVex 返回 -1 表示顶点不存在。两个条件用短路或连接任何一个不满足都触发重输。这套写法同样适合读顶点时使用能避免报告里提到的输入格式不符合要求时出现循环的问题。5.2 不可达路径的 3000 误判问题前面提到源点到某顶点不可达时D[m] 始终等于 INFINITY。问题在于 Dijkstra 的选最小循环并不检查 D[k] 是否有限它仍然会把 3000 当作最小值选出并加入集合。最终输出层只判断了 final[m] 1 就打印路径长度屏幕上会出现从 A 到 E 的最短路径长度为3000这种误导性输出。修正方式是在输出前判断距离值for (m 0; m G-vexnum; m) { if (m w) continue; if (D[m] INFINITY) printf(从%c到%c不存在路径\n, G-vexs[w], G-vexs[m]); else { printf(从%c到%c的最短路径长度为%d路径是, G-vexs[w], G-vexs[m], D[m]); Short(G, path, m, w); printf(%c\n, G-vexs[m]); } }这段代码把不可达和可达彻底分开可达才调用 Short 输出路径不可达直接打印结论。这也解释了为什么 INFINITY 要单独定义成常量——当你要在多个地方判断是不是无穷大时常量名的可读性和可维护性远超光秃秃的 3000。5.3 时间复杂度 O(n²) 和空间复杂度 O(n²) 怎么推导课设要求分析算法的时空性能。Dijkstra 主循环是两层 for外层 m 从 1 到 n-1共 n-1 轮每轮找最小值遍历 n 次松弛又遍历 n 次总操作次数约 2n(n-1)时间复杂度 O(n²)。存储上邻接矩阵本身 n×n加上三个长度 n 的一维数组空间复杂度 O(n²)。对比优化方向如果换邻接表存储找最小值用优先队列选最小的复杂度从 O(n) 降到 O(log n)松弛只遍历出边而不是全部顶点整体复杂度可以降到 O((ne)log n) 级别。但这已经超出课程设计的基本要求更多是工程和面试里的考察点模板在第 6 章给出。5.4 一个可运行的验证用例用下面这组有向图数据验证整套流程顶点A B C D E 弧A,B,6 A,C,3 C,B,1 B,D,5 C,D,3 C,E,4 D,E,2 源点A手动推演一遍A 直接到 B 是 6但 A-C-B 是 314更短A 到 D 可以是 A-B-D459或 A-C-D336取 6A 到 E 可以是 A-C-E347或 A-C-D-E3328取 7。程序输出的最短路径和长度应该严格符合下表否则要检查 final 或 path 的更新逻辑。源点 A 到目标顶点最短路径长度输出路径B4A,C,BC3A,CD6A,C,DE7A,C,E注意 B-D 这条弧权值是 5但经过它到 D 是 459比 A-C-D 的 6 大所以最终最短路径没有走它。这正是 Dijkstra 贪心选择绕路不如走近路的体现也是验证算法没有误选较长路径的关键数据。6. 从课设到工程堆优化模板与答辩经验6.1 把两个隐患改掉再谈优化课设代码要变成可用的最短路径程序有两处必须改一是输出层显式判断 D[m] INFINITY把 3000 翻译成不存在路径二是 path[w] -100 这个哨兵值严格说是危险设计改成在输出路径时判断 i w 更干净避免对 path 数组做越界访问。6.2 邻接表加堆的 Dijkstra 模板当图变成稀疏图邻接矩阵的 O(n²) 空间和时间都不划算工程里更常用邻接表配优先队列#include queue #include vector using namespace std; typedef pairint, int PII; // first 存距离second 存顶点编号 void dijkstra(int s, vectorvectorPII g, vectorint dist) { priority_queuePII, vectorPII, greaterPII pq; dist[s] 0; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; // 过期状态直接跳过等效于 final 标记 for (auto [v, w] : g[u]) if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } }if (d ! dist[u]) continue 替代了课设代码里的 final 数组同一个顶点可能入队多次堆顶弹出时如果距离和当前 dist 不一致说明这是旧状态直接丢弃。松弛逻辑和课设代码完全一致只是把遍历所有顶点找最小改成从堆顶取最小把遍历矩阵改成遍历出边列表。对比着看第 4 章的代码能更清楚 Dijkstra 的本质其实就是三步初始化、取最小、松弛。6.3 课程设计答辩怎么说这份报告被问得最多的三个问题为什么选邻接矩阵Dijkstra 为什么不能有负权边最短路径是怎么输出出来的。回答时把第 2.1 的选型比较、第 2.2 的贪心前提、第 4.3 的前驱数组回溯串起来说再补一句稀疏图会用邻接表加优先队列把复杂度降到 O((ne)log n)基本就能把重心落到算法本质上。本文还有配套的精品资源点击获取