简介数据结构课程设计报告——Dijkstra算法求最短路径是一份面向计算机专业学生与算法初学者的完整课程设计范例。报告围绕单源最短路径问题完整呈现了从问题分析与任务定义、数据结构选择与概要设计到详细设计与编码、上机调试的规范流程。内容涵盖带权有向图的存储与建立、邻接矩阵显示、递归函数应用以及Dijkstra算法最短路径求解并配置了测试用例、调试错误记录与算法时空性能分析帮助读者厘清实现思路与报告撰写框架。资源为单个doc文档大小182KB结构紧凑适合直接参考或按需修改。已有321人浏览学习对于正在完成数据结构课程设计或希望掌握图论经典算法应用的同学这份报告提供了可复用的框架、关键代码思路与排错经验能有效提升课程设计的完成质量。1. 为什么课程设计都选Dijkstra最短路径问题到底在解决什么在数据结构课程设计里最短路径是出现频率最高的选题之一而Dijkstra算法又是其中最稳的“标准答案”。原因并不复杂这个题目把图论、贪心策略、线性表和树形结构全部串了起来又能在有限的代码量内展示完整的数据组织与算法流程。Dijkstra算法解决的是带权图中从单个源点出发到其余所有顶点的最短路径问题时间复杂度可以做到O(V²)甚至O(E log V)边界清晰验证直观。这篇内容会从数据结构选型、C语言实现、测试与报告撰写、再到堆优化与常见陷阱完整走一遍课程设计需要覆盖的路径。适合正在做数据结构课设、准备答辩或者复习考研数据结构与算法时想一次搞懂Dijkstra细节的读者。2. 从数据结构视角拆解Dijkstra算法存储选型与松弛操作2.1 邻接矩阵还是邻接表先看图的规模Dijkstra算法的输入是一张带权图而图的存储方式直接决定算法的实现难度和性能表现。数据结构课程设计里最常见的两种存储是邻接矩阵和邻接表。邻接矩阵是一个V×V的二维数组g[i][j]表示顶点i到j的权值不连通时通常用一个大数比如INF0x3f3f3f3f填充。它的优点是实现简单查询任意两点之间是否有边只需要O(1)时间缺点是空间占用固定为O(V²)当顶点数超过1000时矩阵就需要大约4MB内存int类型如果到5000个顶点就接近100MB这在课程设计的评测环境下很快就会碰到瓶颈。邻接表则用数组链表或vector存储每个顶点的出边只保存实际存在的边空间复杂度为O(VE)。对于稀疏图E远小于V²邻接表是更合理的选择但代码量会增加遍历某个顶点的所有邻居时要通过指针或链表逐个访问。常见的课程设计要求是顶点数在50到500之间。这个规模下邻接矩阵的实现最直观而且排序、查找和打印路径时不容易出错。但如果报告里想体现对数据结构的理解深度可以在“设计分析”一节写明稠密图E接近V²选邻接矩阵稀疏图选邻接表并给出两者的复杂度对比表。存储结构空间复杂度查询边权遍历邻居适用场景邻接矩阵O(V²)O(1)O(V)稠密图、顶点数≤1000邻接表O(VE)O(度)O(度)稀疏图、顶点数大这里有一个关键点Dijkstra算法本身并不依赖存储结构依赖的是“取最小未访问顶点”这一步的实现方式。用邻接矩阵时可以暴力扫描所有未访问顶点一趟O(V)总共V趟所以是O(V²)用邻接表配合优先队列可以把取最小值的开销降到O(log V)从而得到O((VE) log V)的总体复杂度。这份对比写入课程设计的“方案比较”小节是答辩时很加分的内容。2.2 松弛操作贪心策略成立的前提Dijkstra算法的思想一句话就能概括每次从未确定最短路径的顶点中选一个当前dist值最小的顶点u把u标记为已确定然后尝试用u去更新它的所有邻居v更新条件就是著名的松弛公式if (dist[u] g[u][v] dist[v]) { dist[v] dist[u] g[u][v]; }松弛操作的前提是图中不存在负权边因为一旦有负权边已确定的最短路径可能被后来的负边修正贪心选择就不再成立。这个前提必须在报告的“算法原理”部分明确写出否则答辩老师一定会追问。用代码骨架来表示松弛过程会更加清晰。以下是一个用C语言实现的单轮松弛// dist: 源点到各顶点的当前最短距离 // visited[i]: 顶点i是否已经确定最短路径 // u: 本轮选出的dist值最小的未访问顶点 for (int v 0; v n; v) { // 只处理未确定且存在边的顶点 if (!visited[v] g[u][v] INF) { // 松弛操作经u到v比原来的路径更短就更新 if (dist[u] g[u][v] dist[v]) { dist[v] dist[u] g[u][v]; pre[v] u; // 记录v的前驱为u用于还原路径 } } }这段代码的关键在于pre[v] u这一行。前驱数组pre是还原最短路径的唯一依据缺了它程序只能输出最短距离输出不了路线。很多课设报告只贴了dist更新不写pre数组导致“求最短路径”变成了“求最短距离”这是评分中被扣分最常见的原因。dist数组和visited数组是Dijkstra算法的两大支柱。dist记录的是当前已知的最短路径估计值它在算法运行过程中只减不增visited记录的是哪些顶点的估计值已经变成确定值。两者配合才能保证每次选出的u一定是尚未确定且当前距离最小的顶点。理解这两层含义后面看完整实现的代码就不会觉得数组操作繁琐。2.3 优先队列与暴力扫描两种实现路线对比除了邻接矩阵暴力扫描另一个常见实现是邻接表优先队列最小堆。两者的核心区别在“从未访问顶点中选dist最小”这一步。这个选择不仅影响复杂度也影响代码结构和调试方式所以进报告前先把两者的差异想清楚。暴力扫描的写法是每轮用一个for循环遍历所有顶点找出!visited[i] dist[i]最小的那个时间复杂度O(V)。优先队列则是把(dist, 顶点)二元组装进最小堆每次弹出堆顶即是当前最小值但要注意一个顶点可能被多次入堆弹出时如果visited已经为真则跳过这种“懒删除”写法在实现上更省事。两种路线各有适合的题目场景。课程设计如果只要求10到100个顶点暴力扫描代码量少、逻辑直白足够应付。如果设计题目里包含“网络拓扑图”“城市间最短路径”等动辄上千顶点的描述优先队列版本能明显体现效率优势也更容易在答辩时讲出复杂度优化过程。建议在报告里把两种方案都以伪代码形式给出并注明各自的适用条件。3. 课程设计报告的完整实现C语言版Dijkstra最短路径代码3.1 数据结构定义与初始化课程设计报告需要先交代数据结构的定义。下面是一份适合报告正文粘贴的C语言定义使用邻接矩阵存储有向带权图。#include stdio.h #include string.h #define MAXV 100 // 最大顶点数 #define INF 0x3f3f3f3f // 正无穷表示不连通 typedef struct { int edges[MAXV][MAXV]; // 邻接矩阵edges[i][j]表示i到j的边权 int n; // 顶点数 int e; // 边数 } MGraph; int dist[MAXV]; // 源点到各顶点的最短距离 int pre[MAXV]; // 各顶点的前驱顶点 int visited[MAXV]; // 是否已确定最短路径这里的MAXV设为100是为了匹配大多数课程设计的规模要求。INF选择0x3f3f3f3f而不是999999是因为它接近int最大值的1/2两个INF相加仍小于int上限不会出现溢出后反而变小的问题。这个细节写进报告说明里能体现出对边界情况的考虑。图结构定义好后需要一个初始化函数把邻接矩阵填成INF再把对角线edges[i][i]填成0因为顶点到自身的距离是0而不是无穷。边信息的读入可以用文件也可以交互输入常见做法是先用文件保存测试数据方便反复运行验证。void initGraph(MGraph *g) { // 初始化邻接矩阵所有边权先设为INF for (int i 0; i g-n; i) { for (int j 0; j g-n; j) { if (i j) { g-edges[i][j] 0; // 自身到自身距离为0 } else { g-edges[i][j] INF; // 默认不连通 } } } }初始化完成后按照测试文件里的边的信息逐条赋值即可。注意有向图和无向图的赋值区别无向图需要edges[i][j] edges[j][i] w有向图只赋值一次。课程设计题目如果没有明确说明通常按有向图处理但报告里应写清楚这一假设。如果题目要求的顶点数更大比如500个顶点只需要把MAXV改成500并重新编译。这里需要意识到一个问题邻接矩阵是静态二维数组栈上分配空间有限20万字节左右的数组可以通过再大就要考虑用malloc动态分配或改用邻接表。这一点如果写进报告的“不足与改进”能防止答辩中被问“MAXV不够怎么办”。3.2 Dijkstra核心算法完整函数接下来是算法的核心函数。为了让代码可以直接放进报告采用“暴力扫描邻接矩阵”的经典版本这一版本与数据结构教材里严蔚敏版的思路一致便于和理论部分对应。同时这个版本不依赖任何第三方库在DEV-C、Code::Blocks和VS的C模式下都能直接编译避免课设答辩时因为环境差异出现编译错误。void dijkstra(MGraph *g, int start) { // 初始化dist、pre和visited数组 for (int i 0; i g-n; i) { dist[i] g-edges[start][i]; pre[i] start; // 先假定所有顶点直接和源点相连 visited[i] 0; } visited[start] 1; // 源点已确定 // 主循环每次确定一个顶点的最短路径共n-1轮 for (int cnt 0; cnt g-n - 1; cnt) { int u -1; int minDist INF; // 第一趟扫描找未访问顶点中dist最小者 for (int i 0; i g-n; i) { if (!visited[i] dist[i] minDist) { minDist dist[i]; u i; } } if (u -1) { break; // 剩余顶点均不可达提前终止 } visited[u] 1; // 标记u的最短路径已确定 // 第二趟扫描用u更新所有未访问邻居的dist for (int v 0; v g-n; v) { if (!visited[v] g-edges[u][v] INF dist[u] g-edges[u][v] dist[v]) { dist[v] dist[u] g-edges[u][v]; pre[v] u; // 更新前驱记录路径来源 } } } }这段代码的逻辑分成三个部分初始化、选顶点、松弛更新。第一趟扫描中的u -1是一个保护判断当所有剩余顶点都不可达时循环会提前结束而不是继续空转。这个判断在实验报告里值得单独说明因为很多测试数据包含不连通顶点如果没有这个保护程序会把INF当作最小值继续处理。初始化时pre[i] start看起来是把所有顶点的前驱默认为源点但实际路径还原时会发现如果某个顶点j与源点不连通它的pre值即使指向start也是无意义的。路径还原函数里必须判断dist[j] INF才能输出完整路径否则会出现“不连通也打印路径”的错误结果。从循环结构上看这个函数的时间复杂度是O(V²)外层循环V-1轮每一轮里第一趟扫描和第二趟扫描各需要O(V)总操作次数大约为2V²。对于课程设计常见的V≤100规模这个时间可以忽略不计但把V换成5000就要做约5000万次基本操作在限时1秒的评测环境下已经偏紧。这也是为什么堆优化版本值得在报告里出现。3.3 路径输出与数据文件格式有了pre数组还原路径是从终点倒推到源点。这里用递归实现最直观但要注意递归深度不超过顶点数100个顶点完全没有压力。递归写法比循环栈实现更贴近“从后往前找前驱”的思路也更容易在报告中用文字描述。void printPath(int start, int v) { if (v start) { printf(%d, start); // 递归回到源点先打印源点编号 return; } printPath(start, pre[v]); // 先递归打印前驱 printf( - %d, v); // 回到当前层时打印自己 }调用时先判断终点是否可达如果dist[end] INF直接输出“不可达”。这里有一个非常典型的错误不判INF就递归可能因为pre数组未正确初始化而死循环。报告里可以在“测试结果与分析”一节专门留一段说明对不可达顶点的处理策略。完整的主函数流程是读入顶点数、边数初始化图读入边表输入源点和终点调用dijkstra最后打印最短距离和最短路径。边表数据文件建议按如下格式组织每一行表示一条有向边。字段含义见下表。6 8 0 1 10 0 2 5 1 2 2 1 3 1 2 1 3 2 3 9 2 4 2 3 4 4字段含义取值范围6顶点数1 ~ MAXV8边数0 ~ V*(V-1)有向图0 1 10边顶点0到顶点1权值10顶点编号非负权值为非负整数第一行的6和8分别表示顶点数和边数顶点编号从0开始。这份格式简洁易读也方便用脚本批量生成随机测试图。报告里可以把测试文件放入“附录”并在正文中说明每个字段的含义。注意代码中的顶点编号从0开始如果课程设计题目要求从1开始编号只需要在读边时将两个端点各自减1输出路径时再加1其余逻辑不用改。4. 测试用例设计与报告撰写让结果可复现、可答辩4.1 构造有代表性的测试图课程设计报告有些学校叫数据结构实验报告评分时老师最关注的就是测试用例是否能说明问题。一种常见做法是使用前面那段6顶点8条边的图因为它同时包含多条最短路径候选、重边现象和不可达顶点能覆盖算法的核心分支。先手动演算这组数据源点0到顶点4的最短路径是0→2→4距离为7到顶点3的最短路径是0→2→1→3距离为11也可以走0→2→3距离为14所以不走。从0出发顶点5没有出现在边表中因此从0到5不可达。这三个结论分别与代码运行后的输出对照就能验证实现的正确性。这组数据里1→2是一条权值2的有向边2→1是一条权值3的有向边属于典型的有向非对称边不是重边。重边指的是相同起点和终点存在多条边比如0→1同时有权值10和8。邻接矩阵遇到重边只能保留一条常见的做法是保留最小权值因为最短路径不会选择更大的那条。读入边表时需要加一句if (w g-edges[u][v]) g-edges[u][v] w;否则后读入的大权值会覆盖掉之前的较小值。这个处理逻辑在4.1节的测试说明中应当写明。手动演算过程要写进报告的“算法验证”部分不能只贴输出截图。比较规范的做法是画一张表格列出每一轮迭代后dist数组的更新情况如下表所示。轮次选中的顶点u更新后的dist数组顶点0到4说明初始-0, 10, 5, INF, INF源点0的直连边第1轮20, 8, 5, 14, 7经2更新1、3、4第2轮10, 8, 5, 9, 7经1更新3第3轮30, 8, 5, 9, 73没有可优化的邻居第4轮40, 8, 5, 9, 7全部确定这张表能直观说明贪心策略的每一步选择也是答辩时讲解算法过程最好的提词器。注意第2轮之后dist[3]从14降为9说明经过0→2→1→3比直接0→2→3更短这就是松弛操作的实际效果。4.2 运行交互与输出分析完整程序的运行效果可以通过命令行交互展示。常见做法是把程序编译成可执行文件后读取测试数据文件并让用户输入源点和终点输出最短距离和路径。这一步也是截图里最需要保留完整信息的环节下面给出编译命令和一组标准输入输出。# 编译并运行 gcc dijkstra.c -o dijkstra ./dijkstra data.txt程序内的交互逻辑是先读取data.txt中的图数据然后提示输入源点与终点。以下是一组典型输入输出可以直接作为报告中的“程序运行展示”素材。请输入源点: 0 请输入终点: 4 从0到4的最短距离为: 7 最短路径为: 0 - 2 - 4为了验证pre数组还原的准确性可以输入源点0终点3输出应为0 - 2 - 1 - 3。再输入终点5输出应为“不可达”对应4.1节表中INF的处理分支。这三组输出覆盖了最短路、次短路径更新和不可达三种情况足以应对答辩时“换个终点跑一下”的提问。程序代码中可以加入一个调试开关在算法运行后逐行打印dist数组的每一轮变化。这个功能平时不用但写报告时非常有用能直接截取中间数据放进4.1节的表格里避免手算错误。4.3 报告结构和答辩要点课程设计报告通常要求包含“需求分析、概要设计、详细设计、测试与分析、心得与体会”几大块。Dijkstra算法这个选题的信息量足够填满这些章节但需要避免把大段代码直接复制的低级写法。常见做法是把核心代码以注释版放入“详细设计”而“概要设计”部分放结构体说明和模块划分。每个部分都要对应一个可被追问的知识点报告章节必写内容答辩可能的提问需求分析输入输出格式、图的规模为什么不考虑负权边概要设计邻接矩阵还是邻接表稠密图和稀疏图的复杂度详细设计松弛操作的代码注释pre数组如何还原路径测试分析中间表 输出截图不可达顶点如何显示心得与体会暴力扫描 vs 堆优化1000个顶点时怎么改进答辩中最容易被问到的其实是“如果顶点数变成5000你的程序会怎样”。这个问题只要在报告里提前算一笔账5000×5000的邻接矩阵需要占用约100MB内存同时O(V²)的时间复杂度运行时间会显著增加。如果能顺势提出改用邻接表优先队列的方案把复杂度降到O((VE)log V)这个回答基本就是满分。报告里引用代码时建议用等宽字体并把行号去掉避免老师按行号提问时和本地版本对不上。所有截图统一缩放宽度尽量只截命令行窗口的核心输出不要带无关的窗口边框和桌面壁纸。5. 边界情况与进阶优化让课设不再止步于“能跑”5.1 负权边与不可达顶点两个一定会被追问的例外Dijkstra算法不能在存在负权边的图中使用这一点几乎所有教材都会写但课程设计实测中依然常见两类误用。第一类是把负权边赋值为-1表示“无边”导致松弛条件被错误触发dist数组出现跳变。正确做法是无边用INF边权只允许非负值并在边表读入时加断言检查。第二类是忽略不可达顶点在输出时不做INF判断结果打印出类似0 - 5 - ...的假路径。处理方式是在printPath调用前先检查dist[end]是否小于INF或者用visited[end]判断终点是否已被确定。如果题目明确要求处理负权边Dijkstra就不适用了需要换Bellman-Ford或SPFA课程设计的题目描述里如果出现“负权”就不要选Dijkstra算法做核心免得在报告里解释不清。5.2 堆优化版本的核心差异把暴力扫描换成最小堆代码改动集中在“选未访问最小顶点”这一步。C语言标准库没有现成的堆结构常见做法是手写二叉堆或用C的priority_queue。课程设计若允许使用Cpriority_queue的代码量比手写堆小很多// 用优先队列存储(dist, v)pair默认按第一关键字升序 priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; pq.push({0, start}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (visited[u]) continue; visited[u] 1; for (auto [v, w] : adj[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } }visited在堆优化版本中的作用是“元素出堆时再判断”这允许同一个顶点多次入堆但只有dist最小的那次会真正执行更新。这种“懒删除”写法比入堆前判断visited更简洁报告里可以对比两种写法的差别。选定题目用哪种语言以课程要求为准但堆优化的思路要写进报告的“算法改进”小节。5.3 快速验证算法正确性的技巧课程设计报告交稿前可以用一个只有3个顶点的小图做冒烟测试0-1权值11-2权值10-2权值3那么从0到2的最短路径必定是0→1→2、距离2而不是直连的3。如果程序输出与手算一致再跑一遍4.1节的数据。这比直接跑大图更容易定位错误来源因为顶点越少越容易在调试器中跟踪dist数组的变化。答辩前把这两个测试数据截图保存在报告附录里以备现场演示时环境出现异常。本文还有配套的精品资源点击获取
简介数据结构课程设计报告——Dijkstra算法求最短路径是一份面向计算机专业学生与算法初学者的完整课程设计范例。报告围绕单源最短路径问题完整呈现了从问题分析与任务定义、数据结构选择与概要设计到详细设计与编码、上机调试的规范流程。内容涵盖带权有向图的存储与建立、邻接矩阵显示、递归函数应用以及Dijkstra算法最短路径求解并配置了测试用例、调试错误记录与算法时空性能分析帮助读者厘清实现思路与报告撰写框架。资源为单个doc文档大小182KB结构紧凑适合直接参考或按需修改。已有321人浏览学习对于正在完成数据结构课程设计或希望掌握图论经典算法应用的同学这份报告提供了可复用的框架、关键代码思路与排错经验能有效提升课程设计的完成质量。1. 为什么课程设计都选Dijkstra最短路径问题到底在解决什么在数据结构课程设计里最短路径是出现频率最高的选题之一而Dijkstra算法又是其中最稳的“标准答案”。原因并不复杂这个题目把图论、贪心策略、线性表和树形结构全部串了起来又能在有限的代码量内展示完整的数据组织与算法流程。Dijkstra算法解决的是带权图中从单个源点出发到其余所有顶点的最短路径问题时间复杂度可以做到O(V²)甚至O(E log V)边界清晰验证直观。这篇内容会从数据结构选型、C语言实现、测试与报告撰写、再到堆优化与常见陷阱完整走一遍课程设计需要覆盖的路径。适合正在做数据结构课设、准备答辩或者复习考研数据结构与算法时想一次搞懂Dijkstra细节的读者。2. 从数据结构视角拆解Dijkstra算法存储选型与松弛操作2.1 邻接矩阵还是邻接表先看图的规模Dijkstra算法的输入是一张带权图而图的存储方式直接决定算法的实现难度和性能表现。数据结构课程设计里最常见的两种存储是邻接矩阵和邻接表。邻接矩阵是一个V×V的二维数组g[i][j]表示顶点i到j的权值不连通时通常用一个大数比如INF0x3f3f3f3f填充。它的优点是实现简单查询任意两点之间是否有边只需要O(1)时间缺点是空间占用固定为O(V²)当顶点数超过1000时矩阵就需要大约4MB内存int类型如果到5000个顶点就接近100MB这在课程设计的评测环境下很快就会碰到瓶颈。邻接表则用数组链表或vector存储每个顶点的出边只保存实际存在的边空间复杂度为O(VE)。对于稀疏图E远小于V²邻接表是更合理的选择但代码量会增加遍历某个顶点的所有邻居时要通过指针或链表逐个访问。常见的课程设计要求是顶点数在50到500之间。这个规模下邻接矩阵的实现最直观而且排序、查找和打印路径时不容易出错。但如果报告里想体现对数据结构的理解深度可以在“设计分析”一节写明稠密图E接近V²选邻接矩阵稀疏图选邻接表并给出两者的复杂度对比表。存储结构空间复杂度查询边权遍历邻居适用场景邻接矩阵O(V²)O(1)O(V)稠密图、顶点数≤1000邻接表O(VE)O(度)O(度)稀疏图、顶点数大这里有一个关键点Dijkstra算法本身并不依赖存储结构依赖的是“取最小未访问顶点”这一步的实现方式。用邻接矩阵时可以暴力扫描所有未访问顶点一趟O(V)总共V趟所以是O(V²)用邻接表配合优先队列可以把取最小值的开销降到O(log V)从而得到O((VE) log V)的总体复杂度。这份对比写入课程设计的“方案比较”小节是答辩时很加分的内容。2.2 松弛操作贪心策略成立的前提Dijkstra算法的思想一句话就能概括每次从未确定最短路径的顶点中选一个当前dist值最小的顶点u把u标记为已确定然后尝试用u去更新它的所有邻居v更新条件就是著名的松弛公式if (dist[u] g[u][v] dist[v]) { dist[v] dist[u] g[u][v]; }松弛操作的前提是图中不存在负权边因为一旦有负权边已确定的最短路径可能被后来的负边修正贪心选择就不再成立。这个前提必须在报告的“算法原理”部分明确写出否则答辩老师一定会追问。用代码骨架来表示松弛过程会更加清晰。以下是一个用C语言实现的单轮松弛// dist: 源点到各顶点的当前最短距离 // visited[i]: 顶点i是否已经确定最短路径 // u: 本轮选出的dist值最小的未访问顶点 for (int v 0; v n; v) { // 只处理未确定且存在边的顶点 if (!visited[v] g[u][v] INF) { // 松弛操作经u到v比原来的路径更短就更新 if (dist[u] g[u][v] dist[v]) { dist[v] dist[u] g[u][v]; pre[v] u; // 记录v的前驱为u用于还原路径 } } }这段代码的关键在于pre[v] u这一行。前驱数组pre是还原最短路径的唯一依据缺了它程序只能输出最短距离输出不了路线。很多课设报告只贴了dist更新不写pre数组导致“求最短路径”变成了“求最短距离”这是评分中被扣分最常见的原因。dist数组和visited数组是Dijkstra算法的两大支柱。dist记录的是当前已知的最短路径估计值它在算法运行过程中只减不增visited记录的是哪些顶点的估计值已经变成确定值。两者配合才能保证每次选出的u一定是尚未确定且当前距离最小的顶点。理解这两层含义后面看完整实现的代码就不会觉得数组操作繁琐。2.3 优先队列与暴力扫描两种实现路线对比除了邻接矩阵暴力扫描另一个常见实现是邻接表优先队列最小堆。两者的核心区别在“从未访问顶点中选dist最小”这一步。这个选择不仅影响复杂度也影响代码结构和调试方式所以进报告前先把两者的差异想清楚。暴力扫描的写法是每轮用一个for循环遍历所有顶点找出!visited[i] dist[i]最小的那个时间复杂度O(V)。优先队列则是把(dist, 顶点)二元组装进最小堆每次弹出堆顶即是当前最小值但要注意一个顶点可能被多次入堆弹出时如果visited已经为真则跳过这种“懒删除”写法在实现上更省事。两种路线各有适合的题目场景。课程设计如果只要求10到100个顶点暴力扫描代码量少、逻辑直白足够应付。如果设计题目里包含“网络拓扑图”“城市间最短路径”等动辄上千顶点的描述优先队列版本能明显体现效率优势也更容易在答辩时讲出复杂度优化过程。建议在报告里把两种方案都以伪代码形式给出并注明各自的适用条件。3. 课程设计报告的完整实现C语言版Dijkstra最短路径代码3.1 数据结构定义与初始化课程设计报告需要先交代数据结构的定义。下面是一份适合报告正文粘贴的C语言定义使用邻接矩阵存储有向带权图。#include stdio.h #include string.h #define MAXV 100 // 最大顶点数 #define INF 0x3f3f3f3f // 正无穷表示不连通 typedef struct { int edges[MAXV][MAXV]; // 邻接矩阵edges[i][j]表示i到j的边权 int n; // 顶点数 int e; // 边数 } MGraph; int dist[MAXV]; // 源点到各顶点的最短距离 int pre[MAXV]; // 各顶点的前驱顶点 int visited[MAXV]; // 是否已确定最短路径这里的MAXV设为100是为了匹配大多数课程设计的规模要求。INF选择0x3f3f3f3f而不是999999是因为它接近int最大值的1/2两个INF相加仍小于int上限不会出现溢出后反而变小的问题。这个细节写进报告说明里能体现出对边界情况的考虑。图结构定义好后需要一个初始化函数把邻接矩阵填成INF再把对角线edges[i][i]填成0因为顶点到自身的距离是0而不是无穷。边信息的读入可以用文件也可以交互输入常见做法是先用文件保存测试数据方便反复运行验证。void initGraph(MGraph *g) { // 初始化邻接矩阵所有边权先设为INF for (int i 0; i g-n; i) { for (int j 0; j g-n; j) { if (i j) { g-edges[i][j] 0; // 自身到自身距离为0 } else { g-edges[i][j] INF; // 默认不连通 } } } }初始化完成后按照测试文件里的边的信息逐条赋值即可。注意有向图和无向图的赋值区别无向图需要edges[i][j] edges[j][i] w有向图只赋值一次。课程设计题目如果没有明确说明通常按有向图处理但报告里应写清楚这一假设。如果题目要求的顶点数更大比如500个顶点只需要把MAXV改成500并重新编译。这里需要意识到一个问题邻接矩阵是静态二维数组栈上分配空间有限20万字节左右的数组可以通过再大就要考虑用malloc动态分配或改用邻接表。这一点如果写进报告的“不足与改进”能防止答辩中被问“MAXV不够怎么办”。3.2 Dijkstra核心算法完整函数接下来是算法的核心函数。为了让代码可以直接放进报告采用“暴力扫描邻接矩阵”的经典版本这一版本与数据结构教材里严蔚敏版的思路一致便于和理论部分对应。同时这个版本不依赖任何第三方库在DEV-C、Code::Blocks和VS的C模式下都能直接编译避免课设答辩时因为环境差异出现编译错误。void dijkstra(MGraph *g, int start) { // 初始化dist、pre和visited数组 for (int i 0; i g-n; i) { dist[i] g-edges[start][i]; pre[i] start; // 先假定所有顶点直接和源点相连 visited[i] 0; } visited[start] 1; // 源点已确定 // 主循环每次确定一个顶点的最短路径共n-1轮 for (int cnt 0; cnt g-n - 1; cnt) { int u -1; int minDist INF; // 第一趟扫描找未访问顶点中dist最小者 for (int i 0; i g-n; i) { if (!visited[i] dist[i] minDist) { minDist dist[i]; u i; } } if (u -1) { break; // 剩余顶点均不可达提前终止 } visited[u] 1; // 标记u的最短路径已确定 // 第二趟扫描用u更新所有未访问邻居的dist for (int v 0; v g-n; v) { if (!visited[v] g-edges[u][v] INF dist[u] g-edges[u][v] dist[v]) { dist[v] dist[u] g-edges[u][v]; pre[v] u; // 更新前驱记录路径来源 } } } }这段代码的逻辑分成三个部分初始化、选顶点、松弛更新。第一趟扫描中的u -1是一个保护判断当所有剩余顶点都不可达时循环会提前结束而不是继续空转。这个判断在实验报告里值得单独说明因为很多测试数据包含不连通顶点如果没有这个保护程序会把INF当作最小值继续处理。初始化时pre[i] start看起来是把所有顶点的前驱默认为源点但实际路径还原时会发现如果某个顶点j与源点不连通它的pre值即使指向start也是无意义的。路径还原函数里必须判断dist[j] INF才能输出完整路径否则会出现“不连通也打印路径”的错误结果。从循环结构上看这个函数的时间复杂度是O(V²)外层循环V-1轮每一轮里第一趟扫描和第二趟扫描各需要O(V)总操作次数大约为2V²。对于课程设计常见的V≤100规模这个时间可以忽略不计但把V换成5000就要做约5000万次基本操作在限时1秒的评测环境下已经偏紧。这也是为什么堆优化版本值得在报告里出现。3.3 路径输出与数据文件格式有了pre数组还原路径是从终点倒推到源点。这里用递归实现最直观但要注意递归深度不超过顶点数100个顶点完全没有压力。递归写法比循环栈实现更贴近“从后往前找前驱”的思路也更容易在报告中用文字描述。void printPath(int start, int v) { if (v start) { printf(%d, start); // 递归回到源点先打印源点编号 return; } printPath(start, pre[v]); // 先递归打印前驱 printf( - %d, v); // 回到当前层时打印自己 }调用时先判断终点是否可达如果dist[end] INF直接输出“不可达”。这里有一个非常典型的错误不判INF就递归可能因为pre数组未正确初始化而死循环。报告里可以在“测试结果与分析”一节专门留一段说明对不可达顶点的处理策略。完整的主函数流程是读入顶点数、边数初始化图读入边表输入源点和终点调用dijkstra最后打印最短距离和最短路径。边表数据文件建议按如下格式组织每一行表示一条有向边。字段含义见下表。6 8 0 1 10 0 2 5 1 2 2 1 3 1 2 1 3 2 3 9 2 4 2 3 4 4字段含义取值范围6顶点数1 ~ MAXV8边数0 ~ V*(V-1)有向图0 1 10边顶点0到顶点1权值10顶点编号非负权值为非负整数第一行的6和8分别表示顶点数和边数顶点编号从0开始。这份格式简洁易读也方便用脚本批量生成随机测试图。报告里可以把测试文件放入“附录”并在正文中说明每个字段的含义。注意代码中的顶点编号从0开始如果课程设计题目要求从1开始编号只需要在读边时将两个端点各自减1输出路径时再加1其余逻辑不用改。4. 测试用例设计与报告撰写让结果可复现、可答辩4.1 构造有代表性的测试图课程设计报告有些学校叫数据结构实验报告评分时老师最关注的就是测试用例是否能说明问题。一种常见做法是使用前面那段6顶点8条边的图因为它同时包含多条最短路径候选、重边现象和不可达顶点能覆盖算法的核心分支。先手动演算这组数据源点0到顶点4的最短路径是0→2→4距离为7到顶点3的最短路径是0→2→1→3距离为11也可以走0→2→3距离为14所以不走。从0出发顶点5没有出现在边表中因此从0到5不可达。这三个结论分别与代码运行后的输出对照就能验证实现的正确性。这组数据里1→2是一条权值2的有向边2→1是一条权值3的有向边属于典型的有向非对称边不是重边。重边指的是相同起点和终点存在多条边比如0→1同时有权值10和8。邻接矩阵遇到重边只能保留一条常见的做法是保留最小权值因为最短路径不会选择更大的那条。读入边表时需要加一句if (w g-edges[u][v]) g-edges[u][v] w;否则后读入的大权值会覆盖掉之前的较小值。这个处理逻辑在4.1节的测试说明中应当写明。手动演算过程要写进报告的“算法验证”部分不能只贴输出截图。比较规范的做法是画一张表格列出每一轮迭代后dist数组的更新情况如下表所示。轮次选中的顶点u更新后的dist数组顶点0到4说明初始-0, 10, 5, INF, INF源点0的直连边第1轮20, 8, 5, 14, 7经2更新1、3、4第2轮10, 8, 5, 9, 7经1更新3第3轮30, 8, 5, 9, 73没有可优化的邻居第4轮40, 8, 5, 9, 7全部确定这张表能直观说明贪心策略的每一步选择也是答辩时讲解算法过程最好的提词器。注意第2轮之后dist[3]从14降为9说明经过0→2→1→3比直接0→2→3更短这就是松弛操作的实际效果。4.2 运行交互与输出分析完整程序的运行效果可以通过命令行交互展示。常见做法是把程序编译成可执行文件后读取测试数据文件并让用户输入源点和终点输出最短距离和路径。这一步也是截图里最需要保留完整信息的环节下面给出编译命令和一组标准输入输出。# 编译并运行 gcc dijkstra.c -o dijkstra ./dijkstra data.txt程序内的交互逻辑是先读取data.txt中的图数据然后提示输入源点与终点。以下是一组典型输入输出可以直接作为报告中的“程序运行展示”素材。请输入源点: 0 请输入终点: 4 从0到4的最短距离为: 7 最短路径为: 0 - 2 - 4为了验证pre数组还原的准确性可以输入源点0终点3输出应为0 - 2 - 1 - 3。再输入终点5输出应为“不可达”对应4.1节表中INF的处理分支。这三组输出覆盖了最短路、次短路径更新和不可达三种情况足以应对答辩时“换个终点跑一下”的提问。程序代码中可以加入一个调试开关在算法运行后逐行打印dist数组的每一轮变化。这个功能平时不用但写报告时非常有用能直接截取中间数据放进4.1节的表格里避免手算错误。4.3 报告结构和答辩要点课程设计报告通常要求包含“需求分析、概要设计、详细设计、测试与分析、心得与体会”几大块。Dijkstra算法这个选题的信息量足够填满这些章节但需要避免把大段代码直接复制的低级写法。常见做法是把核心代码以注释版放入“详细设计”而“概要设计”部分放结构体说明和模块划分。每个部分都要对应一个可被追问的知识点报告章节必写内容答辩可能的提问需求分析输入输出格式、图的规模为什么不考虑负权边概要设计邻接矩阵还是邻接表稠密图和稀疏图的复杂度详细设计松弛操作的代码注释pre数组如何还原路径测试分析中间表 输出截图不可达顶点如何显示心得与体会暴力扫描 vs 堆优化1000个顶点时怎么改进答辩中最容易被问到的其实是“如果顶点数变成5000你的程序会怎样”。这个问题只要在报告里提前算一笔账5000×5000的邻接矩阵需要占用约100MB内存同时O(V²)的时间复杂度运行时间会显著增加。如果能顺势提出改用邻接表优先队列的方案把复杂度降到O((VE)log V)这个回答基本就是满分。报告里引用代码时建议用等宽字体并把行号去掉避免老师按行号提问时和本地版本对不上。所有截图统一缩放宽度尽量只截命令行窗口的核心输出不要带无关的窗口边框和桌面壁纸。5. 边界情况与进阶优化让课设不再止步于“能跑”5.1 负权边与不可达顶点两个一定会被追问的例外Dijkstra算法不能在存在负权边的图中使用这一点几乎所有教材都会写但课程设计实测中依然常见两类误用。第一类是把负权边赋值为-1表示“无边”导致松弛条件被错误触发dist数组出现跳变。正确做法是无边用INF边权只允许非负值并在边表读入时加断言检查。第二类是忽略不可达顶点在输出时不做INF判断结果打印出类似0 - 5 - ...的假路径。处理方式是在printPath调用前先检查dist[end]是否小于INF或者用visited[end]判断终点是否已被确定。如果题目明确要求处理负权边Dijkstra就不适用了需要换Bellman-Ford或SPFA课程设计的题目描述里如果出现“负权”就不要选Dijkstra算法做核心免得在报告里解释不清。5.2 堆优化版本的核心差异把暴力扫描换成最小堆代码改动集中在“选未访问最小顶点”这一步。C语言标准库没有现成的堆结构常见做法是手写二叉堆或用C的priority_queue。课程设计若允许使用Cpriority_queue的代码量比手写堆小很多// 用优先队列存储(dist, v)pair默认按第一关键字升序 priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; pq.push({0, start}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (visited[u]) continue; visited[u] 1; for (auto [v, w] : adj[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } }visited在堆优化版本中的作用是“元素出堆时再判断”这允许同一个顶点多次入堆但只有dist最小的那次会真正执行更新。这种“懒删除”写法比入堆前判断visited更简洁报告里可以对比两种写法的差别。选定题目用哪种语言以课程要求为准但堆优化的思路要写进报告的“算法改进”小节。5.3 快速验证算法正确性的技巧课程设计报告交稿前可以用一个只有3个顶点的小图做冒烟测试0-1权值11-2权值10-2权值3那么从0到2的最短路径必定是0→1→2、距离2而不是直连的3。如果程序输出与手算一致再跑一遍4.1节的数据。这比直接跑大图更容易定位错误来源因为顶点越少越容易在调试器中跟踪dist数组的变化。答辩前把这两个测试数据截图保存在报告附录里以备现场演示时环境出现异常。本文还有配套的精品资源点击获取
