简介：一份围绕Dijkstra算法求最短路径的数据结构课程设计报告，面向需要完成同类课设任务的高校学生及希望深入理解单源最短路径实现的算法初学者。内容以中南大学课程设计为框架，覆盖问题分析与任务定义、数据结构选择与概要设计、详细设计与编码、上机调试四大环节，详细展示了带权有向图的存储建立、点结构体定义、邻接矩阵显示、递归函数应用及最终最短路径输出的完整过程。报告同时给出测试用例、调试中的错误处理记录及算法时间与空间性能分析，并附有测试结果与学习心得体会。资源包内共1个doc文档，大小182KB，目录层次清晰，便于直接参考章节撰写课程设计报告。这份资源目前已有321人学习或下载，具有较好的课程设计借鉴价值。
1. 为什么课程设计躲不开Dijkstra：从导航到图论的一步之遥
你打开地图搜“从图书馆到东门取快递”，导航给出的不是直线距离，而是一条包含转弯、红绿灯和路段长度的综合路径。换成数据结构课程设计里那道“Dijkstra算法求最短路径”，本质是把交通网络抽象成一张带权图：节点是路口，边是路段，权重是长度或通行代价，然后从某个起点出发，计算到其余所有节点的最短路径长度和经过哪些节点。这个场景覆盖了绝大多数课设题目，校园导航、物流配送、网络拓扑，甚至游戏地图寻路，都落在这套模型上。
课程设计报告要求的不只是“把代码跑出结果”，还要写清楚存储结构为什么这样选、为什么每次选中的点是全局最优、负权边为什么处理不了。这些问题在原理上稍绕，却是答辩老师最爱追问的点。这篇博文按课设交付顺序来讲：先建立图模型和算法逻辑，再给一份能直接改写的C++代码，然后是测例设计、常见坑和报告结构，最后用一个打表验证技巧让代码的每一步都能当面讲清楚。适合正在做数据结构课设、复习考研数据结构或工作中需要快速捡回最短路径算法的读者。
2. 先理解Dijkstra的贪心逻辑：存图方式、松弛操作与负权边的坑
2.1 用邻接矩阵还是邻接表：课设最常见的两种存图方案
Dijkstra处理的是有权图G(V, E)，V是顶点集合，E是边集合。存储方式决定了后续代码结构，也直接决定了能处理的数据规模。课设里节点少则几十、多则上万，两种方案各有适用场景。
| 存图方式 | 空间复杂度 | 边查询 | 适用场景 |
|---|---|---|---|
| 邻接矩阵 | O(V²) | O(1)，直接访问g[u][v] | 节点数≤1000，稠密图，代码直观 |
| 邻接表（vector存pair） | O(V+E) | O(度数)，遍历邻居 | 节点数大、稀疏图，配优先队列 |
| 链式前向星 | O(V+E) | O(度数)，数组模拟链表 | 竞赛常用，课设也可选 |
我的建议是第一版用邻接矩阵跑通逻辑，第二版改成邻接表加优先队列，报告里正好能写两种实现的复杂度对比，回答“为什么做优化”就有具体数据支撑。邻接表推荐直接用STL的vector，不推荐手写链表，指针管理在Delete边或析构时容易漏内存，对课设来说没有额外收益。
2.2 松弛操作：为什么“当前最小距离”可以确定为最终距离
算法核心可以拆成两个动作：选择一个当前dist最小的未访问顶点u；然后遍历u的所有出边，尝试更新邻居v的距离，更新条件是：
dist[u] + w(u, v) < dist[v] 时，把dist[v]改成dist[u] + w(u, v)，同时记录v的前驱为u。
“遍历出边更新邻居”这个动作在教材里叫松弛，对应英文relaxation。选择u这一步用的是贪心策略，可行性建立在“所有边权非负”之上。因为边权非负，从起点到u的任何后续路径都必然先绕到某个未访问节点再折回u，这条绕路路径的长度不会小于当前dist[u]。所以u一旦被选中，dist[u]就已经是最终答案，之后不再需要修改。
提示：如果图中存在负权边，上面这套逻辑立刻失效。负权边可能让已经确定最短路径的节点通过绕路得到更小值；如果存在负权环，最短路理论上没有最小值。遇到负权图要换成Bellman-Ford或SPFA。
这里还有一个常见误用：有的教材把“每次选最小dist”实现成两层循环，内层扫描所有未访问节点，这没有问题；但如果你提前写了visited标记，却又在dist更新后没有跳过旧状态，就会重复处理同一节点。堆优化版本里这个问题的标准解法是弹出时检查d是否大于dist[u]，大于则丢弃，这一行代码在后续实现里很重要。
2.3 一维pre数组与二维path数组：路径还原的不同层次
很多教材在讲完dist数组后，会用一维pre数组记录每个顶点在最短路径上的前驱。输出从起点s到某终点t的路径时，从t往前回溯，直到s再反转顺序就行。这个方案适合单源单终点的输出。
如果题目要求“输出从任意起点到任意终点的所有最短路径”，一维pre就不够用了。常见做法是维护一个二维数组path，每运行一次Dijkstra就填充一行，path[i][v]表示从i到v的前驱节点；最终能还原任意点对路径。检索里常见的说法“所有n-1条最短路径可以用二维数组path”指的就是这个。需要注意的是，不要用一次Dijkstra得到的pre去还原任意点对，路径根本不会经过起点，这是课设报告里最容易写错的部分。
3. 用C++实现Dijkstra：邻接表+优先队列的完整可运行代码
3.1 邻接表里的pair怎么设计
邻接表g[u]保存u的所有出边，每个出边用pair表示。C++标准库的pair默认按first升序排序，所以把边的权重放first、邻居节点号放second，优先队列排序时就无需自定义比较函数。这个细节能省不少代码，也能避免写错仿函数。
3.2 核心实现与一个可直接运行的最小示例
下面这段代码以无向带权图为例，输入第一行是n m，表示节点数和边数；接下来m行是u v w，表示一条边及权重；最后输入起点s。输出起点到每个节点的最短距离与完整路径，节点编号从0开始。
#include <bits/stdc++.h> using namespace std; const int N = 105; const int INF = 0x3f3f3f3f; // 约10.6亿，两个INF相加不超int范围 int n, m, s; vector<pair<int, int> > g[N]; // first=权重，second=邻居节点号 int dist[N], pre[N]; // pre[v]=v在最短路径上的前驱 void dijkstra(int s) { // 0x3f按字节填充，dist每个元素都等于INF memset(dist, 0x3f, sizeof(dist)); memset(pre, -1, sizeof(pre)); // 小顶堆：pair排序时先比较权值，再比较节点号 priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq; dist[s] = 0; pq.push(make_pair(0, s)); // 起点入堆 while (!pq.empty()) { int d = pq.top().first; // 当前取出的距离 int u = pq.top().second; // 当前取出的节点 pq.pop(); // 堆里残留的旧状态，直接丢弃 if (d > dist[u]) continue; // 遍历u的所有出边，执行松弛 for (int i = 0; i < (int)g[u].size(); i++) { int w = g[u][i].first; // 这条边的权重 int v = g[u][i].second; // 邻居节点 if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pre[v] = u; // 记录前驱 pq.push(make_pair(dist[v], v)); // 新状态入堆 } } } } void printPath(int s, int t) { if (dist[t] == INF) { cout << "no path from " << s << " to " << t << endl; return; } vector<int> path; for (int v = t; v != -1; v = pre[v]) { path.push_back(v); } reverse(path.begin(), path.end()); for (int i = 0; i < (int)path.size(); i++) { if (i) cout << " -> "; cout << path[i]; } cout << endl; } int main() { cin >> n >> m; for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; g[u].push_back(make_pair(w, v)); g[v].push_back(make_pair(w, u)); // 无向图加双向边 } cin >> s; dijkstra(s); for (int i = 0; i < n; i++) { cout << "dist[" << i << "] = " << dist[i] << ", path: "; printPath(s, i); } return 0; }代码逻辑可以分四步理解：初始化阶段把所有距离置为INF、前驱置为-1，然后把起点距离置0并压入堆；循环阶段不断弹出距离最小的节点，如果堆里的距离大于dist中记录的值，说明这条状态已经过时，直接跳过；松弛阶段遍历当前节点的所有出边，尝试把邻居v的距离缩小，成功后记录前驱并压入新状态；路径还原阶段从终点沿pre数组回溯到起点再反转输出。
| 参数 | 作用 | 注意事项 |
|---|---|---|
| g[N] | 邻接表 | 元素为(w, v)，顺序写反会导致松弛读取错误 |
| dist[N] | 当前最短距离 | 算法结束时是最终距离 |
| pre[N] | 前驱数组 | -1表示起点或无前驱 |
| pq | 优先队列 | 保证每轮拿到最小距离候选 |
最大的坑就在pair顺序上。C++的pair默认排序先看first，所以g[u]里存(w, v)时first是权重；一旦写成(v, w)，优先队列排序结果完全错误，而且g[u][i].first被当成节点号，运行时不报错但结果全错。如果觉得pair可读性差，换成自定义Edge结构体后，需要在priority_queue里重载比较运算符，工作量其实更大。
3.3 路径还原的边界细节
pre[v]的更新时机是“松弛真正发生”的时候，也就是dist[u] + w < dist[v]成立时才把pre[v]设为u。用小于号而不是小于等于号有一个效果：当两条路径距离相同时，保留原来的前驱，不产生不必要的变化。如果题目要求输出“所有最短路径中任意一条”，这个行为没有问题；如果要求保留所有等价路径，需要额外维护每个节点的前驱集合。
printPath从终点t开始回溯：for循环里的v = pre[v]让v不断向前移动，直到pre值为-1，也就是起点。这里不用额外记录起点是谁，回溯到pre[v]==-1时自然停在起点。需要注意如果图不连通，dist[t]仍为INF，要单独判断，否则回溯会走进死循环。
3.4 复杂度分析与课设选型建议
朴素版的复杂度是O(V²)，来源是每轮都要在未访问节点中扫描一遍找最小值；堆优化版把找最小值这一步降为O(logV)，每条边最多被松弛一次，总复杂度O((V+E)logV)。稠密图里E接近V²，堆优化优势不明显；稀疏图里两者差距非常大，节点数从一千涨到十万，朴素版基本无法运行。
课程设计如果数据范围小，比如城市数n≤50，交朴素版就够，报告里还能顺带比较“朴素实现”和“堆优化实现”的时间差距。如果题目给了大数据文件，直接上堆优化版，并且报告写明“优先队列保证每次O(logV)取到最小值，因此总开销为O((V+E)logV)”。两种版本的代码本质只有堆操作的区别，核心松弛逻辑完全一致，先写朴素版再改成堆优化，比一上来就写堆更容易排查错误。
4. 把课设从代码变成报告：测例设计、排错与答辩要点
4.1 数据结构课程设计报告的结构怎么映射
一份能拿高分的数据结构课设报告，通常包含需求分析、概要设计、详细设计、测试分析和总结。每个部分和本文代码的对应关系大致如下：
| 报告章节 | 对应内容 | 写作重点 |
|---|---|---|
| 需求分析 | 问题描述、输入输出定义 | 定义节点、边、权重的含义，说明要输出什么 |
| 概要设计 | 图的ADT与存储结构选择 | 说明为何选邻接表+优先队列 |
| 详细设计 | 函数接口与核心流程 | 用图表列出dijkstra、printPath的输入输出 |
| 测试分析 | 测试数据、运行截图、复杂度实测 | 含边界测例和异常输入 |
| 总结 | 算法优缺点与改进方向 | 可以提Floyd的全源对比、负权图的限制 |
写详细设计时最忌讳把整段源码贴上去。报告正文只保留核心函数签名、参数表格和一段话的设计说明，完整代码放附录，评审要看代码时再翻附录。需求分析里把“路径规划”与“最短路径”联系起来的段落要写清楚，这是课程设计的立题所在。
4.2 五个必测用例：重边、孤立点、零权边、大图、多组数据
| 用例 | 输入要点 | 期望结果 | 易错点 |
|---|---|---|---|
| 常规连通图 | 普通带权图 | 所有dist有值 | 前驱数组被上一组数据残留污染 |
| 重边 | 0-1出现权重3和5 | 自动取3 | 邻接表保存两条边，松弛后只留小的 |
| 零权边 | 0-1权重0、1-2权重2 | dist[2]=2 | 判断用<，不要用<=，避免零权环增加日志 |
| 孤立点 | 某节点无任何边 | dist保持INF | 输出时判断INF，不能当数字打印 |
| 大规模随机图 | n=10000, m=100000 | 1秒内出结果 | 邻接矩阵会爆内存，必须用邻接表 |
多组数据是课设里容易忽略的。如果题目要求一次运行处理多组询问，每组都要重新调用一次dijkstra，那init部分的reset就必须包含dist、pre和每个vector的clear。我自己的习惯是在dijkstra函数内部完成所有重置，外部不依赖上一次运行的状态，这样每组数据独立，不会互相污染。
提示：输出dist为INF的节点时，不能直接打印整数。写成
dist[i] == INF ? "INF" : to_string(dist[i])，报告里能区分“不可达”和“距离非常大”，也更符合真实场景。
4.3 五个高频运行异常与排查方向
| 异常现象 | 可能原因 | 处理方式 |
|---|---|---|
| 段错误 | 节点号越界，或vector未初始化 | 检查下标从0还是1开始，数组开N+5 |
| 输出全为0 | memset的size写错 | 检查sizeof(dist)是否被写错 |
| 路径打印死循环 | pre回溯不到起点 | 检查起点pre未被正确初始化 |
| 运行超时 | 用了朴素版本且V很大 | 换成优先队列堆优化版 |
| 数值异常 | 用INT_MAX参与加法导致溢出 | 改用0x3f3f3f3f或long long |
INF的选取是这个实验里最经典的问题。INT_MAX加上任意正权边会直接溢出成负数，导致松弛判断完全失效。0x3f3f3f3f约等于10.6亿，两个这样的数相加约21.2亿，仍在int范围内不会溢出。如果权重上限很大，比如达到1e9且路径跨越多条边，dist数组应改成long long，INF换成长整型版本的0x3f3f3f3f3f3f3f3f。
4.4 答辩高频对比：BFS、Floyd、SPFA与Dijkstra
| 算法 | 适用场景 | 复杂度 | 限制 |
|---|---|---|---|
| BFS | 无权图 | O(V+E) | 不能处理带权边 |
| Dijkstra | 非负权图、单源 | O((V+E)logV) | 无法处理负权边 |
| Floyd | 任意图、全源 | O(V³) | 小规模好用，负权环不可 |
| SPFA/Bellman-Ford | 负权边无负环 | 最坏O(VE) | 有负环时不能收敛 |
答辩最常问的一句是“为什么不用BFS”。答案很简单：BFS按层扩展只能保证边数最少，边数少不等于权重总和最小，一旦边带权，BFS的“第一层先到达”策略就失效。把这张表放进报告或答辩PPT里，基本能应对算法选型类提问。
5. 打表验证法：让代码行为在报告和答辩现场都能被讲清楚
最后一招是打表验证法，这也是我调试图算法最常用的手段。Dijkstra跑出正确结果只是第一步，课设评审更看重“你能解释每一步为什么这样走”。常见做法是在每次弹出节点u后打印当前选中的节点和整个dist数组，形成一张过程表，直接放进报告的测试分析部分。
调试输出函数可以这样写：
void debugPrint(int step, int u, int dist[], int n) { cout << "step " << step << ": choose " << u << ", dist = "; for (int i = 0; i < n; i++) { if (dist[i] == INF) cout << "INF "; else cout << dist[i] << " "; } cout << endl; }调用位置放在if (d > dist[u]) continue;之后，这样打印出来的是每个节点第一次被当作最小值处理时的完整状态，正好对应贪心策略的核心决策点。
拿一个具体例子验证。四个节点的图，边为0-1权重5、0-2权重2、1-2权重1、2-3权重3，起点为0。手推结果应该是：dist[0]=0, dist[1]=3, dist[2]=2, dist[3]=5，路径0->2->1和0->2->3。
程序运行日志应逐轮对应：
| 轮次 | 被选中节点 | 松弛更新后的dist数组 |
|---|---|---|
| 1 | 0 | dist[1]=5, dist[2]=2 |
| 2 | 2 | dist[1]=3, dist[3]=5 |
| 3 | 1 | 无更新 |
| 4 | 3 | 无更新 |
把这张表复制进课程设计的测试分析部分，然后运行一次同样输入的代码，把控制台日志截图附在旁边。评审看到“手推结果与程序输出逐行一致”，整套报告的说服力比直接贴运行结果高一个档次；被问到“为什么先选2而不是1”时，也能直接回答因为dist[2]更小，完全照着日志讲就行。这个打表方法不依赖任何框架，五分钟就能接进现有代码。
本文还有配套的精品资源，点击获取
