简介围绕单源点最短路径问题这份C语言实现资料面向学习图结构、准备课程设计或需要理解经典算法的高校学生与初学者。内容以Dijkstra算法为主线结合结构体、指针与图的存储定义完整呈现图的创建与指定起点到其余顶点最短路径的计算过程可对照交通旅游、城市规划、电网架设等路径选择场景理解算法思路。压缩包共2个文件包含1份doc与1份cpp约139KB前者可作设计说明与算法梳理后者为可直接阅读和调试的C语言源码便于把思路落到代码。已有11696人学习适合作为课程设计参考、算法入门对照材料或二次开发起点通过阅读实现细节读者能掌握图的数据组织、最短路径求解流程及常见调试要点并据此扩展自己的路径规划程序。1. 最短路径不是搜出来的是逐个确认出来的大多数人第一次读 Dijkstra注意力都放在每次挑距离最小的那个点上就把它当成一种贪心搜索。其实这个描述倒置了因果关系。这个算法真正在做的事是确认每一轮从候选集合里取出一个距离最小的未确认顶点然后当场宣布——它的最短距离已经定死后面再怎么松弛也不会变小。这个宣布不可撤销没有后悔药。整份代码的正确性、以及所有踩坑的根源都归结到这个不可撤销的断言上。所以如果一份 Dijkstra 实现跑出了错的结果九成不是循环写错了而是某处悄悄破坏了这个断言的前提。接下来要拆的就是这条断言凭什么成立、在 C 里怎么把它实现得又快又不翻车。2. 松弛的本质dist 数组在维护一个会不断收紧的上界2.1 从三角不等式说起dist[v] 到底代表什么先把语义钉死否则后面全是玄学。算法维护一个数组dist[]任意时刻它满足两条不变式dist[v]是一条真实存在的从源点到 v 的路径长度可能是绕远的所以dist[v] 真实最短路而源点dist[src] 0未探索的点是无穷大。换句话说每个dist[v]都是真实答案的一个上界算法在做的只是不断把这个上界往下压直到压不动。压低动作就是松弛。对一条边 (u, v, w)如果dist[u] w dist[v]说明先走到 u 再走这条边比现有方案更短于是更新dist[v] dist[u] w并把 v 的前驱记为 u。这个式子在数学上就是三角不等式取等号的条件最短路必须满足dist[v] dist[u] w对每条边成立。所有松弛都做完且再没有一条边能压下去时这个不等式组的所有约束同时满足dist就收敛成真正的最短路。关键点在于松弛只会让dist变小永远不会变大。这是一种单调收紧也是后面一切复杂度分析和正确性证明的地基。理解了这一点为什么负权边会毁掉一切就不再是死记硬背的结论。2.2 为什么一条边可以被反复松弛而负权边会让它永不收敛考虑一条路径 src → a → b假设先处理了 b 的某条绕远路径dist[b]是个较大的值之后 a 被确认从 a 松弛 bdist[b]变小。这在算法里是常态一个顶点在出堆之前可能被松弛很多次。但由于每轮取出的都是当前dist最小的点而所有边权非负后续任何路径想变得更短都必须先经过一个dist更大的点绕这一圈只会让长度增加。这就是取最小即确认能成立的全部理由——非负边权保证了距离沿着路径单调不减。负权边把这个单调性直接打碎。经典的翻车现场三个点 src、a、b边 src→a 权 2src→b 权 5b→a 权 -4。第一轮取 a距离 2并宣布确认dist[a] 2。第二轮取 b距离 5松弛 b→a 得到dist[a] 1比已确认的 2 还小。此时 a 早就出堆了代码里那段过期快照直接跳过的逻辑会让这次更新再也进不了队列最终结果错得毫无征兆。所以负权不是精度问题而是直接让算法的不变式失效。提示只要图里存在负权边就该换 Bellman-Ford 或 SPFA存在负权环时最短路本身无定义任何算法都只能报负环存在。2.3 复杂度账本O(V²) 和 O(E log V) 谁更快取决于图有多稠朴素实现每轮线性扫一遍所有未确认顶点找最小值扫描 O(V)共 V 轮加上每条边松弛一次 O(E)总计 O(V² E)稠密图下就是 O(V²)。用二叉堆维护候选集后每次取最小 O(log V)每次松弛可能触发一次入堆 O(log V)总代价 O((V E) log V)。但账不能只按渐近看。堆的每次操作有实打实的常数比较、交换、数组下标计算还伴随着随机内存访问。当 E 接近 V² 时log V这个因子反而成了负担朴素版在缓存上还更友好。经验分界线大约在 E 与 V²/log V 同量级附近稠密图上朴素版经常反超。实现方式取最小单次松弛总复杂度适用场景线性扫描数组O(V)O(1)O(V² E)稠密图、V 小于几千二叉堆 惰性删除O(log V)O(log V)O((V E) log V)稀疏图、通用首选索引堆支持 decrease-keyO(log V)O(log V)O(E V log V)堆内元素多、内存敏感斐波那契堆O(log V) 摊还 O(1)摊还 O(1)O(E V log V)理论最优工程上极少用最后一行值得多说一句斐波那契堆的渐近最优是教科书结论但它的常数和实现复杂度让它在实际代码里几乎绝迹。真正写 C 的时候二叉堆加惰性删除是绝大多数场景下的最优解也是这份实现采用的路线。3. 自己动手实现优先队列C 里没有现成的堆3.1 二叉堆的数组布局与上浮下沉C 标准库不提供优先队列qsort只能一次性排序无法支撑边松弛边取最小的动态需求。所以必须自己写一个。二叉堆的好处是它压根不需要指针一棵完全二叉树按层序塞进数组下标 i 的左右孩子是2i1和2i2父节点是(i-1)/2。用无符号右移代替除法还能再省一点因为下标非负。typedef struct { int v; /* 顶点编号 */ long long d; /* 入堆那一刻的距离快照注意是快照不是引用 */ } HeapNode; typedef struct { HeapNode *a; int size; int cap; } MinHeap; static void sift_up(MinHeap *h, int i) { while (i 0) { int p (i - 1) 1; /* 父节点下标右移代替除法 */ if (h-a[p].d h-a[i].d) break; /* 小根堆父不大于子即合法 */ HeapNode t h-a[p]; h-a[p] h-a[i]; h-a[i] t; i p; } } static void sift_down(MinHeap *h, int i) { for (;;) { int l i * 2 1, r l 1, m i; if (l h-size h-a[l].d h-a[m].d) m l; if (r h-size h-a[r].d h-a[m].d) m r; if (m i) break; /* 已满足堆序收工 */ HeapNode t h-a[m]; h-a[m] h-a[i]; h-a[i] t; i m; } }sift_up在插入时把新元素一路往上顶直到父节点不大于它sift_down在弹出堆顶后把数组末尾元素搬到根上再往下沉。两个函数的循环条件都以堆序恢复为终点所以最坏走完整棵树的高度即 O(log n)。注意sift_down里必须先把m i设成默认值再和左右孩子比较否则会出现孩子比父小但没被选中的漏洞。3.2 惰性删除没有 decrease-key 时怎么打补丁教科书上的 Dijkstra 假设堆支持 decrease-key某个顶点的距离变小了就地在堆里调整它的位置。但二叉堆要做到这点必须额外维护一个pos[v]数组记录每个顶点在堆中的下标每次交换都得同步更新代码量和出错概率都上一个台阶。工程上更常见的做法是惰性删除。距离变小时不修改旧元素直接 push 一个新的快照进去同一个顶点在堆里可能同时存在好几份d值各不相同。弹出时比对一下如果这份快照的d比当前dist[v]大说明它是过期的丢掉继续弹下一个。static int heap_push(MinHeap *h, int v, long long d) { if (h-size h-cap) { /* 容量不够就翻倍 */ int nc h-cap ? h-cap * 2 : 16; HeapNode *p realloc(h-a, (size_t)nc * sizeof(HeapNode)); if (!p) return 0; /* 分配失败要能往上报 */ h-a p; h-cap nc; } h-a[h-size].v v; h-a[h-size].d d; sift_up(h, h-size); /* 注意先上浮再自增 */ h-size; return 1; } static int heap_pop(MinHeap *h, HeapNode *out) { if (h-size 0) return 0; /* 空堆必须能安全返回 */ *out h-a[0]; h-a[0] h-a[--h-size]; /* 末尾元素补到根 */ sift_down(h, 0); return 1; }heap_push里先上浮再自增这个顺序很容易写反。sift_up内部读的是h-size所在位置作为新元素的位置如果先自增索引就整体偏了一位堆序会静默损坏——结果时对时错极难排查。heap_pop里--h-size与赋值写在同一行靠的是先减后用的求值顺序读代码时留意一下。代价是什么堆里最多堆积 O(E) 个元素而不是 O(V)。对于稀疏图这完全可接受对于 E 接近 V² 的稠密图内存占用会显著上升这也正好呼应上一节稠密图用朴素版的结论。3.3 主循环三行代码决定了整个算法的正确性把堆接进主循环骨架只有十几行但每一行都承担着正确性职责。/* 返回 1 表示 src 可达 dst0 表示不可达 */ int dijkstra(const Graph *g, int src, int dst, long long *dist, int *prev, MinHeap *h) { const long long INF (long long)1 60; /* 远大于任何真实路径长度 */ for (int i 0; i g-n; i) { dist[i] INF; prev[i] -1; } dist[src] 0; if (!heap_push(h, src, 0)) return -1; /* -1 表示内存分配失败 */ HeapNode cur; while (heap_pop(h, cur)) { int u cur.v; if (cur.d dist[u]) continue; /* 惰性删除过期快照直接丢 */ if (u dst) return 1; /* 目标已确认可提前收工 */ for (int i g-head[u]; i ! -1; i g-edges[i].next) { int v g-edges[i].to, w g-edges[i].w; long long nd dist[u] w; /* 用 long long 算防溢出 */ if (nd dist[v]) { dist[v] nd; prev[v] u; /* 记录前驱供路径回溯 */ if (!heap_push(h, v, nd)) return -1; } } } return 0; /* 堆空了还没到 dst不可达 */ }if (cur.d dist[u]) continue;这一行是惰性删除的落地它同时守住了另一个边界已经确认过的顶点不会因为过期快照被再次展开。少了这一行稠密图上同一个点会被反复展开复杂度直接退化还可能在特定结构上陷入长时间的无效循环。if (u dst) return 1;是可选优化。因为弹出的第一个 dst 一定是最优解此时可以直接返回省下后面所有无关顶点的展开。但要注意一旦提前返回dist数组里其他顶点的值都还是上界而不是最终值如果外部还要读它们这行必须删掉。这就是典型的性能与语义的取舍。long long nd dist[u] w;用 64 位中间变量而不是dist[u] w dist[v]直接比。原因是dist[u]可能等于 INF加上一个正权后溢出回绕成负数条件成立dist[v]被赋成一个荒谬的负值——结果就是不可达的点变成了可达距离还是负的。这个 bug 在 int 版实现里非常普遍。4. 邻接表与内存C 里没有 vector图得自己长出来4.1 链式前向星用数组模拟链表图的存储有三条路。邻接矩阵是 O(V²)V 上万就吃不动只在极稠密或需要频繁查两点连通性时考虑。指针链表每个节点一次 malloc释放时还得逐个 free访问时一路顺着指针跳缓存命中率惨不忍睹。第三条路是链式前向星——用两个数组模拟链表把所有边压进一块连续内存head[u]存第一条边的下标每条边的next指向同起点的下一条边-1表示结束。#define MAXN 100005 #define MAXM 500005 typedef struct { int to; /* 边的终点 */ int w; /* 边权 */ int next; /* 同起点的下一条边在 edges 中的下标-1 表示没有 */ } Edge; typedef struct { int head[MAXN]; Edge edges[MAXM * 2]; /* 无向图每条边存两份有向图只用 MAXM */ int ecnt; int n; } Graph; static void graph_init(Graph *g, int n) { g-n n; g-ecnt 0; for (int i 0; i n; i) g-head[i] -1; /* -1 表示该点暂时无边 */ } static void add_edge(Graph *g, int u, int v, int w) { g-edges[g-ecnt].to v; g-edges[g-ecnt].w w; g-edges[g-ecnt].next g-head[u]; /* 新边插到链表头 */ g-head[u] g-ecnt; } static void add_undirected(Graph *g, int u, int v, int w) { add_edge(g, u, v, w); add_edge(g, v, u, w); /* 无向图必须双向各加一次 */ }add_edge用的是头插法新边的next指向当前head[u]再让head[u]指向新边。这样插入是 O(1)不需要遍历到尾。代价是同一顶点的出边顺序与输入顺序相反但这不影响最短路结果除非你有多条等长路径时取字典序最小这类需求。遍历时写成for (int i g-head[u]; i ! -1; i g-edges[i].next)每次只做一次数组下标访问整个邻接表在内存里是连续的CPU 预取器能吃上劲。相比指针链表实测在百万级边上有数倍差距这不是玄学是缓存行的物理规律。用宏定死MAXN的版本适合题目规模已知的场景。如果规模不确定就把head和edges换成malloc出来的指针并在graph_init里按n和2*m分配。两种写法各有取舍静态数组省掉分配开销、地址确定但要预留最大空间动态分配灵活但多了一层失败处理和释放责任。4.2 路径回溯prev 数组与逆序输出prev[v]记录的是v 的最短路是从哪个点走过来的。它构成一棵以源点为根的最短路树从任意终点顺着prev往上走走到-1就停得到的是从终点到源点的逆序路径。/* 调用前必须确认 dist[dst] ! INF否则会打印出一条只有一个点的假路径 */ int path[MAXN], len 0; for (int cur dst; cur ! -1; cur prev[cur]) { path[len] cur; if (len g-n) break; /* 防御prev 成环时兜底正常不会触发 */ } printf(距离 %lld\n, dist[dst]); for (int i len - 1; i 0; i--) /* 逆序输出才是 src - dst */ printf(%d%s, path[i], i ? - : \n);这个循环有两个隐含前提。第一dist[dst]必须有限否则prev[dst]是-1循环立刻退出path里只有 dst 一个元素输出看起来像找到了一条长度为 0 的路径——这是最容易被漏掉的假阳性。第二prev链必须无环。正常情况下非负权保证无环但如果图里混进负权边松弛可能把一个点的prev指回它的后代回溯就死循环了。len g-n那行是兜底宁可输出一条错路径也不能让程序挂住。4.3 内存布局决定了常数常数决定了能不能过同样叫 O((VE) log V)为什么有的实现快一个数量级差别几乎全在缓存上。堆数组、dist数组、prev数组、head数组都是顺序访问友好edges数组在松弛时按next跳着走虽然是数组但下标不连续属于半随机访问。如果再把Edge结构体塞得太胖比如加了一堆调试字段一个缓存行只能装下两三个边跳转成本立刻翻倍。常见的实现思路是把热字段拆开to和next挨在一起w单独放一个数组或者干脆把结构体压缩到 8 字节以内让一条边正好对齐。这种优化在 V、E 都是十万级的时候未必明显到了百万级就是能不能在时限内跑完的区别。这份实现保留了清晰的三字段结构优先保证可读性需要压常数时按这个方向改就行。5. 常见问题排查五个让结果悄悄错掉的坑5.1 现象不可达的点距离是负数或者跑到一半结果全乱原因几乎一定是INF溢出。dist[u] w里的dist[u]要是INT_MAX加上一个正权就回绕成负数nd dist[v]成立于是把一个不可达点标成了距离 -2147483648。更阴险的是它不会崩只会让后续所有松弛基于这个负值继续算最终结果面目全非。解决办法有两层。第一INF取一个足够大但离类型上限有余量的值比如 int 下取0x3f3f3f3f约 10.6 亿两条这样的值相加都不会溢出。第二中间量用 64 位算long long nd (long long)dist[u] w;让溢出根本没有机会发生。两条同时做最稳妥只做第二条也能兜住。5.2 现象无向图跑出来只有从源点单向可达反向永远到不了原因很简单add_edge只加了一条有向边。无向图的一条边等价于两条方向相反、权值相同的边必须调用两次add_edge而很多人写顺手了只写一次在有向图上测通了就以为没问题换成无向图输入立刻错一半。解决是在接口层就把语义分开提供一个add_undirected封装内部固定调用两次add_edge调用方永远不需要记住该写几条。同时留意edges数组的容量要按2*m开只按m开会在加边时越界写这种越界往往不立即崩溃而是悄悄覆盖掉相邻内存里的head数组症状极其诡异。5.3 现象程序卡死或者在大图上跑到超时三种可能。第一种while (heap_pop(...))依赖的堆没有正确判空size减到 0 之后还在读a[0]读到的是脏数据可能反复入堆形成活锁。第二种缺了if (cur.d dist[u]) continue;同一个顶点被反复展开松弛又不断产生新快照队列只增不减。第三种sift_down的循环条件写错导致堆序永久损坏取出的最小值其实不是最小算法在错误的确认顺序下反复纠正复杂度退化到不可接受。排查顺序建议从堆开始写个几十行的小测试随机 push 一万个数再全部 pop检查输出是否严格非降序。堆对了再看主循环里那行惰性删除的判断有没有漏。两者都没问题再回头查sift_up里先上浮再自增的顺序。5.4 现象路径打印出来是终点在前或者直接段错误逆序问题是没做反向遍历。prev链从 dst 出发天然得到 dst → … → src必须从数组尾部倒着输出。段错误通常出在路径数组的容量上path按MAXN开没问题但如果用变长数组或malloc(n)得确认最坏情况下的路径长度确实不超过n简单路径最多经过 n 个点这个界是安全的。还有一个隐蔽版本当src dst时回溯循环只走一轮就遇到prev[src] -1输出只有源点一个这是正确的但距离是 0 而不是 INF。如果代码里写的是if (dist[dst] INF) return 不可达;这没问题如果写成if (dist[dst] INF)而INF又被定义成某个具体边界值就要小心边界相等时被误判。5.5 现象单个用例跑得对连续跑多组数据从第二组开始全错典型的全局状态没清干净。head数组、ecnt、堆的size三者都必须在新一组数据开始前重置。head忘了清会保留上一组的边ecnt忘了清零会让新边写到旧边上堆的size忘了清零会把上一组的残留元素当成有效数据弹出来——三种都会导致第一组对、后面全错这种极具迷惑性的表现。解决办法是把初始化收拢到一个graph_init和一个heap_reset里测试的main函数在每组数据开头无条件调用不要依赖我记得清了。另外如果堆是malloc出来的程序末尾一定要free(h.a)重复调用时也要先把旧缓冲区释放再初始化否则每一组都泄漏一次长跑测试会吃掉大量内存。6. 设计取舍什么情况下不该继续加码 Dijkstra写到这一步值得回头审视几个选择它们没有唯一正确答案只有适配场景。第一个取舍是堆 vs 线性扫描。前面列的表格已经给出分界线但实际决策还要看两件事图的稀疏程度是否稳定以及实现能不能复用。如果一份代码既要跑随机稀疏图又要跑接近完全的稠密图稳妥做法是两边都实现按E与V*V/8的关系运行时切换代价是多维护一条分支。第二个取舍是intvslong long。全部用long long最省心但dist数组的内存翻倍大图上会明显影响缓存命中。经验做法是距离用long long存边权仍用intINF取(long long)1 60这样既避免了溢出又把最热的edges数组压到最小。这也是这份实现采用的组合。第三个取舍更根本还该不该用 Dijkstra。负权边出现时它直接失效必须换 Bellman-Ford 系列需要求所有点对的最短路时V 次 Dijkstra 未必比 Floyd 差稀疏图上通常是前者更快如果只求单一起终点、且能构造出可采纳的启发函数比如网格图上用曼哈顿距离A* 能把扩展的顶点数砍掉一个数量级图是静态的且查询极频繁时双向 Dijkstra 或者一次预处理加多次查询的路线更划算。场景特征推荐方案理由非负权、单源、稀疏二叉堆 Dijkstra通用性最好实现成熟非负权、单源、稠密线性扫描版 Dijkstra堆的常数反成负担存在负权边Bellman-Ford单调性失效Dijkstra 不适用单一起终点、有启发信息A*可显著减少扩展节点单一起终点、无启发信息双向 Dijkstra从两端同时收敛常能减半验证一份实现对不对我习惯用三层测试第一层用已知答案的小图手算比对第二层和 Floyd 在随机小图上对拍一千组任何一组不一致就说明有 bug第三层构造边界数据——只有一个点、源点等于终点、完全不可达、有自环、有重边、边权为 0、恰好是一条链。这四类边界各跑一遍能捞出来的问题比读十遍代码还多。从那以后我每次写完最短路都强制走一遍对拍 边界用例这套流程哪怕只是改了一个比较符号。曾经有一次把写成小图上完全看不出来跑到一个带重边的用例才炸——这种血泪经验靠肉眼审查是防不住的。这份实现里那几个看起来很啰嗦的防御性判断基本都是这么一条条踩出来的。希望帮到你。本文还有配套的精品资源点击获取