★ FEATURED ARTICLE 简介最短路径Dijkstra算法的C语言课程设计以VC6.0为开发环境利用结构体、指针等基础知识实现图结构完成图的创建与存储并求解单源点最短路径问题适合数据结构课程设计、算法学习及实际应用参考。压缩包内共2个文件包含一份详细介绍算法原理与实现过程的课程设计文档doc和一份完整可编译的C语言源程序cpp整体仅139KB内容紧凑清晰。目前已有11694人学习或下载是被广泛认可的经典实现。借助这份资料读者可理解Dijkstra算法的执行流程获得可运行、可修改的代码框架与配套设计说明直接用于交通旅游、城市规划、电网架设等场景的路径建模也能在此基础上进一步优化和扩展功能快速完成相关课程设计或算法实践。1. 最短路实现前必须先想清楚的事Dijkstra为什么是贪心却不是万能在路径规划、网络路由和游戏寻路里求两点最短路径几乎默认就是 Dijkstra。我在一次 C 代码评审里见过很多次同样的场面算法流程每个人都能背可真把数组、堆、INF 和路径还原拼在一起时五个节点的样例一次过几十万节点的图一跑就出现“玄学”偏差。问题大多不在算法思想而在 C 语言表达里的数据结构选型、溢出处理和堆的细节。下面的内容基于一版实际调试过的 Dijkstra 实现先讲清楚正确性基石和选型理由再给一套完整可编译的 C 代码最后列出五个不翻一次车很难发现的坑。适合要交课程设计、要做城市级路网实验或者想彻底搞懂堆优化 Dijkstra 的开发者。2. 邻接表 二叉堆Dijkstra在C语言里的正确打开方式Dijkstra 算法在 C 语言里的落地第一个选择不是堆而是图的存储结构。很多人上来就写邻接矩阵n 稍微大一点就直接内存爆炸真正能处理几万节点以上的实现几乎都是“邻接表存边 小顶堆维护候选节点”。这一章先把正确性讲透再回答两个选型问题图怎么存、堆怎么选。这两件事定了后面写代码才不会返工。2.1 为什么Dijkstra是“最短路径”问题的贪心模板Dijkstra 的贪心策略可以压缩成一句话每次从“尚未确定最短距离”的节点里选出 dist 值最小的那个 u把 u 标记为已确定然后用 u 去松弛所有出边。这里的“确定”不是拍脑袋它依赖一个关键前提所有边权非负。可以用反证理解假设存在另一条从源点到 u 的更短路径那这条路径从源点出发后第一次离开“已确定集合”时必然经过某个未确定节点 x。既然 u 是当前未确定节点里 dist 最小的那么 dist[x] dist[u]从 x 到 u 剩下的边权又全部非负所以整条备选路径不可能比 dist[u] 更小。于是当前 dist[u] 就是最终值。这个结论决定了算法边界它是单源算法一次运行只能求一个源点到所有点的最短距离它要求边权非负出现负权边贪心基础就直接坍塌。注意它和无权图的 BFS 不是一回事无权图每条边权重相等BFS 是 O(nm) 的天然最优解有权图才轮到 Dijkstra一旦出现负权边就得换 Bellman-Ford 或 SPFA。很多入门者把 Dijkstra 当成“加了权重的 BFS”这是理解上的第一个误区——正确性依赖的是非负权重下的贪心收敛而不是队列展开。2.2 邻接矩阵与邻接表稀疏图里选错结构就翻车邻接矩阵的空间是 O(n²) 的。n 取 10^5 时10^10 个 int 大约是 40GB直接不可行就算 n 降到 5000矩阵能放下Dijkstra 每轮从数组里扫描最小值也要 O(n)整体 O(n²)在实时计算场景里依然不够看。现实里的路网、通信网大多是稀疏图边数 m 通常在 n 的 2 到 3 倍左右邻接表空间 O(nm)遍历一个节点的全部出边总代价是 O(nm)这才是能撑住大图的形态。C 语言里我惯用的邻接表是“链式前向星”用边数组加 head 数组模拟链表而不是每次 malloc 一个节点。定长数组连续分配没有碎片问题预处理阶段一次性分配完遍历时 cache 友好度也比散落的内存节点好。下面是建图骨架第 3 章会基于它组装完整程序。#define MAXN 100005 #define MAXM 200005 typedef struct Edge { int to; // 这条边指向的节点 int w; // 边权 int next; // 同一出边链表中的下一条边下标 } Edge; Edge edges[MAXM]; int head[MAXN]; int edge_cnt; void add_edge(int u, int v, int w) { edges[edge_cnt].to v; edges[edge_cnt].w w; edges[edge_cnt].next head[u]; head[u] edge_cnt; }代码逻辑不复杂head[u]存节点 u 的第一条出边在edges数组中的下标每加一条边用头插法挂到链表头部。add_edge的参数是起点、终点、边权如果是无向图记得调用两次即add_edge(u, v, w); add_edge(v, u, w);否则只建了单向边后续松弛会漏掉一半路径。MAXM在有向图里取最大边数无向图里必须取最大边数的两倍这个容量估算是我见过最多的翻车点之一小了直接数组越界表现出随机崩溃。2.3 堆的选型数组、二叉堆与优先队列无堆的 Dijkstra 每轮都要在未确定节点里扫描最小值复杂度 O(n²)用二叉堆之后push 和 pop 都是 O(log n)每个节点确定一次每条边最多触发一次入堆整体 O((nm)log n)。n10^5、m3×10^5 时前者操作量在 10^10 量级后者大约 10^6 量级差距是两个数量级以上。这也是为什么“堆优化 Dijkstra”几乎成了大图最短路的默认配置。方案时间复杂度适用规模经验值C 语言实现成本邻接矩阵 每轮扫描最小值O(n²)n ≤ 5000 且图较稠密低邻接表 每轮扫描最小值O(n²)小数据或对拍验证低邻接表 手写二叉堆O((nm)log n)n ≤ 10^6 的稀疏图中邻接表 斐波那契堆O(mnlogn)理论更优但常数巨大很高为什么不选斐波那契堆它确实在渐进复杂度上更好看但常数大、实现复杂单个 decrease-key 操作要维护根链表和度数数组单一最短路场景里收益非常有限。工程上和竞赛里手写二叉堆就是最可靠的折中代码短、可控性强、性能足够。如果你的项目允许 CSTL 的priority_queue可以直接用但题目明确了 C 语言实现手写二叉堆就成了必须掌握的技能。下一章就把这个堆和前面的邻接表拼起来。3. 完整可编译的Dijkstra C实现从建图到输出最短路径这一章把第 2 章的Edge、head、add_edge组装成一个可编译文件。为了让读者能跟着步骤走我按“公共常量 → 堆 → 主循环 → main”四块给代码每块都能独立理解拼起来就是完整程序。沿用第 2 章的结构体定义下面的代码不再重复声明。3.1 先定好容量与 INF这些常量要放进公共头区#include stdio.h #include string.h #include stdlib.h #define MAXN 100005 #define MAXM 200005 #define INF 0x3f3f3f3fMAXN是节点数上限MAXM是边数上限如果是无向图MAXM必须写成最大边数的两倍这一点上一条已经强调过。INF用0x3f3f3f3f而不是INT_MAX原因是INT_MAX做dist[u] w时会溢出成负数被松弛条件误判成“更短路径”后面第 4 章会专门展开。这个值大约是 10.6 亿两个相加约 21.2 亿仍然小于 int 上限单次加法不会溢出。3.2 手写二叉堆push、pop 与两个堆化函数typedef struct HeapNode { int u; // 节点编号 int dist; // 该记录对应的 dist 值 } HeapNode; HeapNode heap[MAXN * 4]; int heap_size; int heap_empty(void) { return heap_size 0; } void swap_node(int i, int j) { HeapNode tmp heap[i]; heap[i] heap[j]; heap[j] tmp; } void sift_up(int i) { while (i 1 heap[i].dist heap[i / 2].dist) { swap_node(i, i / 2); i / 2; } } void sift_down(int i) { while (i * 2 heap_size) { int j i * 2; if (j 1 heap_size heap[j 1].dist heap[j].dist) j; if (heap[i].dist heap[j].dist) break; swap_node(i, j); i j; } } void heap_push(int u, int d) { heap[heap_size] (HeapNode){u, d}; sift_up(heap_size); } HeapNode heap_pop(void) { HeapNode top heap[1]; heap[1] heap[heap_size--]; sift_down(1); return top; }堆数组下标从 1 开始而不是 0这样i * 2和i / 2的父子关系计算不需要额外调整。sift_up用在插入后把新元素向上浮sift_down用在弹出堆顶后把最后一个元素向下沉。sift_down里每次先比较左右子节点选出更小的那个再决定是否交换如果父节点已经更小直接跳出这是二叉堆保持堆序的关键。heap_push里的(HeapNode){u, d}是 C99 复合字面量老牌 MSVC 可能不支持遇到编译错误就改成先声明一个临时结构体再赋值。这里要特别留意堆里存的不只是“当前最优候选”一个节点可能因为被多次松弛而入堆多次heap数组容量开MAXN * 4是经验值针对边数较大的图最多入堆次数接近 m保守起见开到MAXM MAXN更安全。堆元素多不代表结果错但会拖慢速度如何过滤旧记录是 3.3 的核心。3.3 松弛主循环出堆判旧的正确姿势int dist[MAXN]; int prev_vertex[MAXN]; int visited[MAXN]; void dijkstra(int src, int n) { for (int i 1; i n; i) { dist[i] INF; prev_vertex[i] -1; visited[i] 0; } dist[src] 0; heap_size 0; heap_push(src, 0); while (!heap_empty()) { HeapNode cur heap_pop(); int u cur.u; if (cur.dist ! dist[u]) continue; // 堆里残留的旧 dist 记录作废 visited[u] 1; for (int e head[u]; e ! -1; e edges[e].next) { int v edges[e].to; int w edges[e].w; if (!visited[v] dist[u] w dist[v]) { dist[v] dist[u] w; prev_vertex[v] u; heap_push(v, dist[v]); } } } }出堆后第一件事是检查cur.dist ! dist[u]这是堆优化 Dijkstra 里最重要的防御。原因同一节点可能被 push 多次比如节点 x 先以 10 入堆后来又被松弛成 5 再次入堆堆里同时存在 (x, 10) 和 (x, 5)。如果不用 dist 比较做过滤旧记录 (x, 10) 先出堆时会把 x 当成已确定节点正确值 5 即使随后出堆也会被visited挡住整棵子树的距离全错。只用visited[u]判断不够稳cur.dist ! dist[u]才是唯一可靠信号。松弛条件里同时判断!visited[v]因为已确定节点的 dist 不可能再被更新。prev_vertex[v] u放在更新的 if 内部记录的是“谁把 v 的 dist 刷新的”这个时机不能错第 4 章会详细说。路径还原用递归实现最直观void print_path(int src, int v) { if (v src) { printf(%d, src); return; } if (prev_vertex[v] -1) { printf(不可达); return; } print_path(src, prev_vertex[v]); printf( - %d, v); }递归打印的缺点是节点很多时调用栈可能很深。工程上如果路径很长改成循环先把路径收集到一个数组里再逆序输出思路和递归完全一样只是不用怕栈溢出。3.4 main与输入输出最小可运行文件int main(void) { int n, m, s; scanf(%d%d%d, n, m, s); memset(head, -1, sizeof(head)); edge_cnt 0; for (int i 0; i m; i) { int u, v, w; scanf(%d%d%d, u, v, w); add_edge(u, v, w); } dijkstra(s, n); for (int i 1; i n; i) { if (dist[i] INF) printf(INF\n); else printf(%d\n, dist[i]); } return 0; }输入格式约定为第一行n m s节点编号 1 到 n后面 m 行每行一条有向边u v w。memset(head, -1, sizeof(head))必须执行否则head里是未初始化的随机值遍历出边时e ! -1的循环终止条件会失效表现为访问到野下标后崩溃。组装时把第 2 章的建图代码、3.1 的常量、3.2 的堆、3.3 的 dijkstra 和这里的 main 按顺序拼进同一个.c文件即可。测试样例可以用三个节点两条边的图手算3 2 1边为1 2 5和2 3 2期望输出是 0、5、7跑通后再加大规模。4. Dijkstra实现避坑五个让结果悄悄变错的细节避坑章节的每一条都来自实际调试经历按“现象 → 原因 → 解决”的顺序写。结果不对的时候先按这个顺序排查通常比看半天代码更有效。4.1 用INT_MAX当INF溢出让dist变成负数现象小数据正常边权稍微放大dist 数组里出现负数程序却把这些负数当成了最短距离。原因INT_MAX加上任意正边权结果直接溢出成负数被dist[u] w dist[v]判断成“更短”于是污染整棵最短路树。解决用0x3f3f3f3f当 INF它约等于 10.6 亿单次加法不超过 21.2 亿远小于 int 上限 21.47 亿。如果最终距离可能超过 20 亿那是另一层问题直接看 4.4。4.2 堆里过期记录不丢弃最短路就算错现象大规模数据偶发一条路径偏长重跑一次可能又好了很难定位。原因节点被多次 push旧记录先出堆时节点还没被标记为 visited旧值就被当成最优值去松弛邻居正确的新值即使随后出堆也会因为 visited 标记被跳过后面的结果就再也修不回来。解决出堆后立刻判断cur.dist ! dist[u]不相等就 continue。这个检查比 visited 判断更严格因为不管旧记录和新记录的出堆顺序如何只要 dist 不匹配就不会被当有效候选。4.3 重边和自环让堆里元素爆炸程序超时现象图规模本身不大但堆 push 次数多得离谱运行时间远超预期。原因多条重边会让同一对节点反复松弛每次成功松弛都往堆里 push 一次自环边权非负时虽然永远松弛不成功但每次遍历到它都会白白做一轮比较和入堆尝试。解决读入时按 (u, v) 合并重边只保留最小边权自环直接跳过。对于无向图add_edge(u, u, w)会被调用两次读入时判断if (u v) continue可以省下不少无意义操作。4.4 距离用int存大图直接翻车现象输出出现很大的负数或者把可达节点判断成 INF。原因真实最短距离超过 int 上限。不要以为0x3f3f3f3f无敌它只是保证“单次加法不溢出”如果边权是 10^9路径经过三跳就接近 3×10^9早就越过 int 边界。解决把dist[]、HeapNode.dist、INF统一升级成 long longINF 用0x3f3f3f3f3f3f3f3fLLprintf 里对应改成%lld。升级类型时最容易漏掉的是堆节点里的 dist 字段漏一个就会出现“比较用了 64 位存储用了 32 位”的截断错。4.5 路径还原的前驱记录时机错了输出全乱现象打印路径只有一跳或者递归半天不结束。原因prev_vertex[v]被赋值在了不该赋值的地方比如在“即将松弛”之前就随手记了一次或者源点的前驱初始化成了 0递归打印时一路回到 0 再继续往前找形成死循环。解决prev_vertex[v] u只放在 dist 被严格更新的 if 里源点的前驱初始化为 -1print_path里先判断-1再递归。如果需要输出“经过的边编号”同样只在更新成功时记录 prev_edge逻辑完全一致。排查时建议打开计数器统计出堆时被丢弃的旧记录数量为零但结果不对问题大概率在松弛条件数量非常大先检查有没有重边和自环。这两步配合上面的 4.1 和 4.4能覆盖绝大多数“结果悄悄变错”的场景。5. 验证与调优怎么确认你的Dijkstra真的最短代码能跑通不等于答案正确。这一章给三个验证手段从对拍、理论自检到性能实验逐步确认实现没有问题再谈调优。5.1 小数据对拍用Floyd验证Dijkstra结果对拍的思路是用一个绝对可信但慢的算法当裁判拿同一份数据跑两个实现逐项比较。Floyd 适合这个角色虽然 O(n³)但正确性一目了然n 取 100 以内时执行没压力。void floyd(int n) { for (int k 1; k n; k) for (int i 1; i n; i) for (int j 1; j n; j) if (A[i][k] A[k][j] A[i][j]) A[i][j] A[i][k] A[k][j]; }A是邻接矩阵初始全部为 INFA[i][i] 0有重边时取最小权。对拍流程用随机数据生成器产出 n、m、边权n 控制在 50 到 100m 随机取 n 到 3n 之间同一份数据分别喂给 Floyd 和 Dijkstra比较每个节点的 dist。如果某条不一致把 n 缩小到 10 以内手动画出图推一遍基本能锁定是建图方向问题、堆过期记录问题还是 INF 问题。写随机生成器时注意边权用正数避免误入负权禁区。5.2 三角不等式全图自检一条循环找出松弛bug最短路径有个天然性质对任意边 (u, v)必须满足dist[v] dist[u] w这被称为最短路三角不等式。跑完 Dijkstra 后遍历一次所有边一旦发现违反该不等式的边说明某个节点的 dist 被算大了。int check_shortest(int n) { for (int u 1; u n; u) { if (dist[u] INF) continue; for (int e head[u]; e ! -1; e edges[e].next) { int v edges[e].to; int w edges[e].w; if (dist[v] dist[u] w) return 0; } } return 1; }返回 0 说明实现有 bug返回 1 也不代表绝对正确但这个检查对溢出、旧记录没过滤、边方向建反这几类问题非常敏感。把它放在测试代码里当断言用每次跑完 Dijkstra 都检查一遍能省下大量肉眼排查时间。5.3 看耗时前先看图的形态链图、网格图与随机图的差异性能测试不能只跑一个图就下结论。我用三类图做基准链图每个节点最多两条边堆里候选很少、网格图m 约 2n接近真实路网、随机稠密图m 接近 n(n-1)/2。计时代码很简单clock_t begin clock(); dijkstra(s, n); double elapsed (double)(clock() - begin) / CLOCKS_PER_SEC; printf(%.3f s\n, elapsed);链图上堆优化和朴素的差距不大因为每轮候选节点本来就少网格图上堆优化的 log 开销显著O(n²) 实现很快无法承受到了接近完全图的稠密图O(n²) 的数组扫描版本反而可能更快因为堆操作的常数是数组扫描的几倍log 因子被常数吃掉。经验判断是当 m/n 小于 20 时优先堆优化接近完全图时重新考虑朴素实现。盲目认定“堆优化一定快”是个常见误区方案选择永远要放在具体图形态里衡量。6. 从手写堆到工程级优化Dijkstra还能再快一步的细节前面五章解决的是“跑对”这一章讲“在跑对的前提下跑更快”。两个方向一个是堆本身的改良一个是先量化再决定优化什么。6.1 索引堆与decrease-key什么时候值得换手写二叉堆加过期丢弃的写法简单可靠但代价是同一节点可能入堆多次堆体积最坏会膨胀到边数 m。如果统计数据里入堆次数超过 n 的两三倍可以考虑换成索引堆额外维护pos[u]表示节点 u 在堆数组里的下标每次 swap_node 时同步交换pos松弛时若 v 已经在堆里直接调小它的 dist 并调用一次 sift_up。这样堆内永远只有 n 个元素省掉大量过期记录占用的入堆和出堆开销。代价是多维护一个数组松弛分支要多判断 v 是否在堆内代码复杂度上升明显。我的习惯是先保留当前写法打印出总 push 次数确认超过阈值再动手换。6.2 先看统计再优化push/pop次数与cache连续性调优不是换算法是量数据。加两个全局计数器push_cnt和pop_cnt主程序结束后打印如果 push_cnt 接近 m 量级说明松弛正常瓶颈在堆操作常数如果远小于 m说明很多边根本没参与松弛先查连通性再考虑优化。另一个方向是内存布局链式前向星本质是数组模拟链表遍历时在edges数组里跳着走边数极大时 cache 命中率会下降如果图特别大、性能测试显示遍历出边很慢可以改成把每个节点的出边连续存放在独立数组里配一个start和degree数组记录边界。这个改动工作量不大但收益要建立在测量之上不要凭感觉重写。我第一次写堆优化 Dijkstra 时也迷信复杂度硬学了斐波那契堆调了三天没通换回手写二叉堆后半天就过了数据。后来养成的习惯是先让朴素实现对拍再上堆最后才谈常数优化每次入堆次数和被丢弃的旧记录数量都要打印出来看一眼。这个习惯帮我躲过不少“数据一换就翻车”的场面。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
