C语言手写Dijkstra最短路径：链式前向星、堆优化与路径还原-北京尧图网络

简介面向图结构学习与课程设计场景这份资料围绕单源点最短路径问题给出基于C语言的Dijkstra算法实现方案适合掌握结构体、指针与基本数据结构后希望理解图的创建、存储及最短路径求解过程的学生和开发者参考。压缩包内共2个文件包含1个doc文档与1个cpp源码整体约139KB文档可用于梳理算法思路与课程设计说明源码便于对照图结构定义、单源最短路径计算及程序组织方式。已有11696人学习说明其在同类课程设计选题中具有一定参考价值。读者可从中了解Dijkstra算法如何落到C程序从图的建图与存储入手完成既定起点到其余顶点的路径计算并可将思路迁移到交通旅游、城市规划、电网架设等路径选择场景同时为A-star等相关算法学习打基础。1. 从一张算错里程的调度表说起Dijkstra 到底解决什么问题某公司的调度后台出过一次事故一批站点的行车里程算出来比实际短了三分之一司机按表走油费对不上。查到最后问题就出在最短路径模块那是一段几年前的 C 代码边权类型用的是 int中转节点的距离累加时溢出回了负数。Dijkstra 是最短路径里最常被点名的一个算法给定一张带非负权重的图和一个起点一次算出起点到其余所有点的最小代价。它不校验图里有没有负环也不处理负权边但在路网、任务依赖、网络跳数这类权重天然非负的场景里它是默认答案。适合谁手上有 C 语言工程、需要把算路逻辑嵌进现有进程、又不想引第三方库的人。下面这份实现按「存图 → 朴素版 → 堆优化 → 路径还原」四层拆开每一层都能单独编译跑起来。2. 邻接表还是邻接矩阵链式前向星的三个结构与四个参数选存储结构这一步很多人会随手写邻接矩阵然后在真实数据上撞墙。矩阵的访问确实快g[u][v]一行就够但它把「没有边」也当数据存下来了。一万个顶点就是一万乘一万个 int四十亿字节进程直接被系统干掉。Dijkstra 每一步只关心「u 有哪些出边」所以正确的做法是按边存让枚举出边的代价只跟出边条数有关。2.1 三种存图方式的代价对比先把账算清楚再动手。下面这张表是我在几个不同规模数据上实测后整理的量级关系不是理论推导可以直接拿去对照自己的场景。方式空间枚举 u 的出边适合规模常见翻车点邻接矩阵int g[V][V]O(V²)O(V)V ≤ 2000 的稠密图V1e5 时静态数组直接编译失败或占满内存边集数组struct{int u,v,w;} e[E]O(E)O(E)只跑一次的最小生成树Dijkstra 需要按点找边用它等于每轮全表扫链式前向星O(VE)O(deg(u))通用1e5 点 1e6 边无压力next写成指向边本身而不是下标链式前向星这个名字听着唬人本质就是「每个顶点挂一条链表链表用数组实现」。它比vectorEdge好在两点一是不做动态分配边池一次性开好运行期没有 malloc 抖动二是删边、清图、多组数据复位都只是改几个计数器缓存友好度也更高。C 语言工程里这套写法基本是标配。2.2 三个数组撑起整张图整份实现的核心就是head、边池、ecnt这三样东西剩下的都是围绕它们的循环。下面这段可以直接贴进头文件。#include stdio.h #include stdlib.h #include string.h #define MAXV 100005 /* 顶点上限按题目/业务规模改留 5% 余量 */ #define MAXE 500005 /* 有向边上限无向图每条边算两条要开两倍 */ typedef long long ll; static const ll INF (ll)4e18; /* 远大于任何可能路径长度且加一个边权不溢出 */ typedef struct { int to; /* 这条边指向的顶点编号 */ int w; /* 边权必须 0Dijkstra 的前提 */ int next; /* 同起点的下一条边在边池里的下标-1 表示链表结束 */ } Edge; static Edge e[MAXE]; static int head[MAXV]; static int ecnt 0; /* 多组数据或换图时调用n 是本组数据的顶点数 */ static void init_graph(int n) { for (int i 0; i n; i) head[i] -1; ecnt 0; } /* 加一条有向边 u - v权重 w */ static void add_edge(int u, int v, int w) { e[ecnt].to v; e[ecnt].w w; e[ecnt].next head[u]; /* 头插新边接在 u 的链表最前面 */ head[u] ecnt; } /* 无向图必须正反各加一次少加一次答案会偏大且不报错 */ static void add_undirected(int u, int v, int w) { add_edge(u, v, w); add_edge(v, u, w); }逻辑上有两点值得展开。head[u]存的是「u 的最后一条入池边」的下标而不是顶点号很多人第一次写会写成next head[u]之外还去改head[u]指向的顶点结果链表断掉。头插法意味着遍历顺序和输入顺序相反这对最短路结果没有影响但如果输出方案时要求字典序最小就需要改成尾插或者事后排序。遍历的标准写法是for (int i head[u]; i ! -1; i e[i].next)i是边的下标e[i].to才是邻居。参数上INF的取值是最容易被忽略的一处。用INT_MAX或LLONG_MAX当无穷大在松弛时做dist[u] w会直接溢出成负数然后这个负数会比所有真实距离都小被当成最优解推广出去。取 4e18 的好处是留出了大约 5e18 的余量任何合理的边长累加都碰不到边界。边权w用int存是为了省内存但累加时必须先转成ll这一点在第 5 章会单独讲。2.3 四个必须在动手前定下来的参数第一个是顶点编号基准。输入里顶点是从 0 还是从 1 开始全篇必须统一init_graph清到n还是n-1、dist数组从哪个下标开始初始化都要跟它对齐。第二个是MAXV / MAXE无向图别忘了乘二重边多的时候边池要按「输入行数」而不是「去重后的边数」来开。第三个是INF。第四个是边权的量纲如果业务里是浮点里程就把w和dist一起换成double同时把INF改成1e300比较时加一个1e-9的容差否则浮点误差会让本该相等的两条路径反复互相松弛。提示把MAXV和MAXE定义成宏放在文件顶部比散落在函数里的字面量安全得多。我在一个项目里见过int head[10000]和一个写着i 100000的循环跑小数据永远正常一上生产就段错误。3. 朴素版 Dijkstra 的 38 行三段循环与松弛条件怎么写才不出错朴素版是所有优化的地基它把算法在做什么暴露得最清楚。整个流程就三段从「还没确定的点」里挑出当前dist最小的那个、把它标记为已确定、用它去更新所有邻居。没有堆没有花哨数据结构三十几行能写完。3.1 状态数组各管什么dist[i]是当前已知的「起点到 i 的最小代价上界」注意是上界不是最终答案vis[i]表示「i 的最短距离是否已经锁定」。这两个数组的语义差别决定了代码正确性dist小不代表答案定了只有vis打过标记才是定了。非负权这个前提保证了一件事在所有未确定的点里dist最小的那个它的dist已经不可能再被任何后续路径改小因为任何绕行都要额外付出非负的代价。这条性质就是整个算法成立的唯一理由也是负权边会让它失效的原因。3.2 完整可编译实现static ll dist[MAXV]; static int vis[MAXV]; /* 朴素 DijkstraO(V^2 E)适合 V 5000 的稠密图 n: 顶点数src: 起点顶点编号 1..n */ void dijkstra_dense(int n, int src) { for (int i 0; i n; i) { dist[i] INF; vis[i] 0; } dist[src] 0; for (int iter 0; iter n; iter) { /* 第一段线性扫描找未确定点里 dist 最小的 */ int u -1; for (int i 1; i n; i) { if (vis[i]) continue; if (u -1 || dist[i] dist[u]) u i; } /* 剩下的点全都不可达提前结束避免把 INF 拿去松弛 */ if (u -1 || dist[u] INF) break; vis[u] 1; /* 第二段锁定 u 的答案 */ /* 第三段松弛 u 的所有出边 */ for (int i head[u]; i ! -1; i e[i].next) { int v e[i].to; ll nd dist[u] (ll)e[i].w; /* 先提升到 64 位再相加 */ if (nd dist[v]) dist[v] nd; /* 只有更优才写回别无条件覆盖 */ } } }三段循环各自的含义需要说清楚。第一段里u -1 ||这个短路判断是必须的否则第一轮dist[u]读的是dist[-1]属于未定义行为有些编译器会读到 0于是每次都挑中 0 号点结果诡异但不崩溃最难查。第二段的vis[u] 1之后不再更新dist[u]这是算法性质决定的不是偷懒。第三段的nd用ll承接是在做加法之前就转换写成dist[u] e[i].w再赋给ll时如果dist[u]本身是llC 语言会自动提升也不会出错但把提升写在明面上更不容易被后人改坏。参数方面src必须在1..n范围内越界会静默写坏dist数组之外的栈内存症状是别的局部变量莫名其妙变值。如果图里有重边不用预处理松弛时会自动取小的那条。如果图里有自环且权为 0无害自环权为正nd一定大于dist[u]也不会写回。3.3 拿一张六个点的图手工推一遍理论讲完最快的验证方式是自己用笔画一遍再跟程序输出对照。取这样一组边1-2(7) 1-3(9) 1-6(14) 2-3(10) 2-4(15) 3-4(11) 3-6(2) 4-5(6) 6-5(9)无向图起点 1。轮次锁定点 udist[u]本轮发生的松弛110d27, d39, d614227d3min(9,17)9 不变d422339d4min(22,20)20d6min(14,11)114611d5205420d5min(20,26)20 不变6520无出边可松弛循环自然结束最终dist [0,7,9,20,20,11]。这张表的价值在于如果程序跑出来d4 22说明第三轮没有执行到或者3-4这条边压根没加进去如果d6 14说明3-6缺失或者松弛条件写成了之外的形式。手工推演一次后面排错速度快十倍。注意迭代次数用n而不是n-1。理论上n-1轮就够了但有些实现里第一轮只是锁定起点用n更不容易差一轮。代价只是一个常数次循环。4. 手写二叉堆把 O(V²) 压到 O(E log V)懒惰删除与对拍验证朴素版慢在哪里慢在第一段的线性扫描。每一轮都要把全图未确定的点扫一遍找最小值n轮下来就是V²。换成小根堆之后取最小值是 O(log V)总复杂度降到 O((VE) log V)稀疏图上差距非常明显。堆不用引库二叉堆四十行就能写完而且比qsort反复排序稳定得多。4.1 什么时候该上堆什么时候不该不是所有场景堆都更快。稠密图E ≈ V²时堆优化里每条边都可能触发一次入堆常数比线性扫描大实测反而更慢顶点数在几千以内、边几乎全连的图朴素版往往赢。经验阈值E和V一个量级稀疏图比如路网平均出度 3~5上堆E接近V²比如完全图或密集的相似度矩阵用朴素版。我一般会两版都留着用编译期开关切跑一跑再定。4.2 堆和懒惰删除typedef struct { ll d; int v; } Node; /* 堆元素距离顶点号 */ static Node heap[MAXE]; /* 容量按边数开不是按点数 */ static int hsize 0; static void heap_push(Node x) { int i hsize; heap[i] x; while (i 1) { /* 上浮比父亲小就换 */ int p i 1; if (heap[p].d heap[i].d) break; Node t heap[p]; heap[p] heap[i]; heap[i] t; i p; } } static Node heap_pop(void) { Node top heap[1]; heap[1] heap[hsize--]; /* 末尾元素提到根再下沉 */ int i 1; for (;;) { int l i 1, r l | 1, m i; if (l hsize heap[l].d heap[m].d) m l; if (r hsize heap[r].d heap[m].d) m r; if (m i) break; Node t heap[m]; heap[m] heap[i]; heap[i] t; i m; } return top; } void dijkstra_heap(int n, int src) { for (int i 0; i n; i) dist[i] INF; hsize 0; dist[src] 0; heap_push((Node){0, src}); while (hsize 0) { Node cur heap_pop(); int u cur.v; if (cur.d dist[u]) continue; /* 懒惰删除这是条过期记录直接丢弃 */ for (int i head[u]; i ! -1; i e[i].next) { int v e[i].to; ll nd cur.d (ll)e[i].w; if (nd dist[v]) { dist[v] nd; heap_push((Node){nd, v}); /* 不删旧条目直接压新的 */ } } } }懒惰删除是这个实现里最省事也最容易看不懂的一处。标准做法是「减小某个元素的键值」需要能定位它在堆里的位置得额外维护一个pos数组写起来繁琐还容易错。懒惰删除换了个思路不定位、不修改直接压一条新记录进堆旧记录留在里面当垃圾。出堆时用cur.d dist[u]判断这条是不是过期的是就丢掉。正确性靠的是「过期记录的 d 一定大于当前 dist[u]」而堆又是小根堆所以真答案一定先出堆。heap开MAXE而不是MAXV是这个实现里最常见的越界来源。每条边最多触发一次 push加上起点那一次总入堆次数不超过E1。有人按顶点数开小图跑得好好的一上真实数据就踩内存而踩内存的表现可能是段错误也可能只是答案偶尔错一次属于典型的黑匣子式故障。4.3 用对拍把两版绑在一起验证写完两个版本别急着删朴素版它是最好的参考答案。随机造图两版各跑一遍逐点比对几百组不出问题再上真实数据。#include time.h /* 随机生成 n 点 m 边的无向连通图跑两版并比对返回不一致的点数 */ int cross_check(int n, int m, unsigned seed) { srand(seed); init_graph(n); for (int i 2; i n; i) /* 先连成一条链保证连通 */ add_undirected(i - 1, i, rand() % 20 1); for (int i 0; i m; i) { int u rand() % n 1, v rand() % n 1; if (u v) continue; add_undirected(u, v, rand() % 100 1); /* 故意制造重边和环 */ } static ll a[MAXV], b[MAXV]; dijkstra_dense(n, 1); memcpy(a, dist, sizeof(ll) * (n 1)); dijkstra_heap(n, 1); memcpy(b, dist, sizeof(ll) * (n 1)); int bad 0; for (int i 1; i n; i) if (a[i] ! b[i]) bad; return bad; /* 非 0 就说明有一版实现有 bug先别怀疑数据 */ }对拍的关键是让随机图覆盖到边界重边、自环候选、不可达点把链去掉就会有、权重恰好相等导致多条最短路的情况。rand() % 100 1保证权重非负这是 Dijkstra 的前提别在对拍里塞负权然后怀疑算法。真需要负权换 Bellman-Ford 或者 Johnson那是另一个话题。5. 排查五个让最短路径悄悄算错的细节这些坑的共同点是「不崩溃、不报错、结果就是不对」只能靠对照和打印中间量定位。每条按现象、原因、解决三段写都是我在真实代码里见过或写出来的。现象一只有起点是 0其余全是 INF。原因通常是编号基准错位。输入顶点是 0-basedinit_graph(n)清到n没问题但主循环从i 1开始扫0 号点永远不参与于是所有边的起点都被当成不存在。解决办法很土但有效在建图函数里加一行断言if (u 1 || u n || v 1 || v n) { fprintf(stderr, bad edge %d-%d\n, u, v); exit(1); }让错位在第一组数据就暴露而不是等到出报表才发现。现象二距离出现巨大负数或者 Dijkstra 跑完后某些点距离比直达还小。原因是INF加边权溢出。dist[u]是INF时dist[u] w在某些类型组合下会绕回负数而负数比任何真实距离都小会被当作更优解继续传播污染一大片。解决办法有两层INF取 4e18 并全程用ll同时在松弛前加一句if (dist[u] INF) continue;兜底。两层都做比只做一层稳。现象三无向图算出来的距离普遍比预期大。add_edge只调了一次。这个错误在无向图里特别隐蔽因为从起点出发的那一半边还在能算出部分结果看起来「像对的」。养成习惯凡是写add_edge(u, v, w)的地方先问一句这张图是有向还是无向无向一律走add_undirected。现象四堆优化版比朴素版慢一个数量级或者跑大数据时段错误。先看heap数组的容量。按MAXV开的堆在边数超过点数时会越界写但小图对拍完全发现不了。再看if (cur.d dist[u]) continue;是不是写成了写成本身不错但会漏掉d dist[u]的有效条目某些图上会导致邻居没被松弛。最稳的验证是打开-fsanitizeaddress重跑一遍对拍堆越界立刻现形。现象五第一组数据全对从第二组开始全错。状态没复位。需要清的至少有三个ecnt在init_graph里、hsize在dijkstra_heap开头、vis在dijkstra_dense开头。dist每次都会重新赋INF一般不用单独清但如果代码里提前break过残留值是脏的。我一般把复位逻辑统一收进一个reset_all(n)里主函数每组数据开头调一次比散落各处可靠。提示调试时不要只打印最终的dist把每一轮锁定的u、dist[u]、被松弛的(v, nd)都打出来跟第 3 章那张手工推演表对一遍通常三轮之内就能定位到是建图错了还是松弛错了。6. 路径还原与上线前的三组验证把 dist 数组变成能看懂的路线距离数字对业务方没什么用他们要的是「从 A 到 B 走哪几条边」。补一个prev数组就够了代价几乎为零。6.1 prev 数组与路径回溯static int prev_node[MAXV]; /* prev_node[v] 最短路树上 v 的父亲 */ /* 在松弛成功的地方加一行 */ if (nd dist[v]) { dist[v] nd; prev_node[v] u; /* 记录是谁把 v 变优的 */ /* 堆优化版这里还要 heap_push(...) */ } /* 回溯从 dst 一路往回走逆序存放最后反转 */ int path[MAXV], len 0; for (int cur dst; cur ! -1; cur prev_node[cur]) { path[len] cur; if (cur src) break; } for (int i 0, j len - 1; i j; i, --j) { int t path[i]; path[i] path[j]; path[j] t; }prev_node必须在初始化时全部置 -1否则回溯会在脏数据上打转甚至死循环。另一个细节是「多条等长最短路」nd dist[v]严格小于只会保留最先发现的那条改成会保留最后发现的那条。业务上如果要「换乘最少」或「高速优先」就得在距离相等时加二级比较而不是简单改符号。6.2 上线前我一定跑的三组验证验证项构造方式期望结果单点自环与重边同一条边加三次权重 5、3、9取 3其余被松弛淘汰不可达点图分成两个不连通块不可达点dist保持INF路径回溯长度 1规模压测1e5 点、5e5 边随机图计时堆优化版应在百毫秒级朴素版直接放弃第三组要顺手看一眼内存dist和prev_node各MAXV边池MAXE条Edge结构体 12 字节5e5 条边约 6MB静态数组全在 BSS 段进程启动时就被映射不会在中途 OOM。真碰到百万级以上的图就把静态数组换成一次性malloc但别在运行期反复申请释放。血泪经验是这三组验证我第一次做的时候只做了第一组结果上线第二天在「不连通块」上翻车回溯函数在prev_node全 -1 的情况下绕着自己转了整整一分钟后被超时杀掉。从那以后我每次交付带路径还原的算路模块都强制把不可达和等长最短路这两组构造出来跑一遍哪怕数据方说「我们图一定是连通的」。希望帮到你。本文还有配套的精品资源点击获取

C语言手写Dijkstra最短路径：链式前向星、堆优化与路径还原

相关推荐

对象数据库选型实战：从ORM阻抗失配到ZODB原型与避坑

Qwen-Image-GGUF常见问题排查完全清单：显存溢出、画面崩坏与文字模糊的10个解决方案

NodeJS开发二手交易平台：技术选型与核心实现

更多资讯

VS Code 差异对比实战指南：4 个对比入口与 4 个窗格搞定 Git 冲突

Dism++ 完整指南：5 分钟完成第一次空间回收，玩转 Windows 深层维护

快速上手 Lively 音频可视化：从安装到桌面随节奏起舞

Ruffle 桌面版播放本地 SWF 文件：快速上手的完整教程

Vorssaint：免费开源的 macOS 菜单栏工具，逐应用音量与系统监控一个图标搞定

2.1GPIO输入

今日更新

AI智能体开发实战：从技术原理到商业落地

OpenShell 完全定制指南：从安装到深度配置，打造高效 Windows 开始菜单

Superpowers技能体系全解析：从Skills引入到安装的完整指南

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？