简介：面向学习图结构与最短路径算法的C/C++初学者及课程设计开发者，这份资料围绕单源点最短路径问题，给出基于Dijkstra算法的求解思路与C语言实现，可服务于交通旅游、城市规划、电网架设等路径选择场景的入门实践。RAR压缩包共2个文件，以1份doc文档和1份cpp源码为主，约139KB；文档侧重算法说明与课程设计过程，源码对应图的创建、存储及单源点最短距离计算，便于对照阅读和调试。已有11696人学习，说明其在同类课程设计资料中具有一定参考度。读者可从中获得图结构定义、指针与结构体运用、Dijkstra算法落地及运行验证的完整样例，也能据此梳理从需求分析到编码实现的课程设计脉络，适合作为算法学习与课程作业的对照材料。

1. 最短路径 Dijkstra 算法 C语言实现：先搞清楚它默认能吃多大的图

拿到一份最短路径 Dijkstra 算法 C语言实现，最先要确认的不是它能不能编译通过，而是它默认的图规模。我见过太多人把邻接矩阵版直接丢到十万个点的图上，样例跑得飞快、结果也对，一上真实数据就卡死，回头翻代码才发现复杂度早就写死在两层 for 循环里。Dijkstra 的思想本身二十分钟就能讲完，难的是工程上的取舍：稠密图用 O(V²) 的矩阵版反而更省心，稀疏图必须上邻接表加堆；边权类型决定了 INF 该取多大；要输出路径就多一个 pre 数组，而且它得跟着松弛一起更新。这份资源把朴素版、堆优化版和配套的图输入约定放在一起，正好能把「能跑通」和「敢拿去用」这两件事一次做完。适合正在准备机试、写路径规划小工具，或者想重新把图论基础打牢的人。

2. 松弛操作与存储选型：为什么矩阵版和堆版都得会

2.1 松弛的数学前提：贪心在什么条件下才成立

Dijkstra 的全部动作只有两个：从「未确定的点集」里挑出 dist 最小的那个点，然后用它去更新邻居的 dist。这个「挑最小」的动作之所以正确，靠的是一条三角不等式：对任意一条从源点 s 到 v 的路径，如果它经过某个还没确定的点 x，那么这条路径的长度一定不小于 dist[x]，而 dist[x] 又不小于当前被挑出来的 dist[u]，所以在边权非负的前提下，这条绕路不可能比 dist[u] 更短。

换句话说，Dijkstra 的贪心是「非负边权」这个条件换来的。一旦图里出现负权边，这个不等式立刻崩掉。举个最小反例：s→a 权重 2，s→b 权重 5，b→a 权重 -4。算法第一轮会挑中 a 并把 dist[a]=2 定死，但真实最短路径是 s→b→a，长度只有 1。这个点已经被标记为「已确定」，后面再也不会被更新，于是结果就错了。

工程上这条性质决定了两个判断：第一，读入边权之后应该扫一遍，只要有负数就直接换 Bellman-Ford 或者 Johnson，别硬套 Dijkstra；第二，如果业务里确实存在「负代价」的语义（比如某种折扣、返还），要确认它是不是能通过平移权重转成正数，转不了就别用这套代码。

常见做法是在读边阶段顺手记一个has_negative标志，跑算法之前先判断一次，比事后 debug 结果对不上要省事得多。

2.2 邻接矩阵与邻接表加堆：一份选型对照表

同一份 Dijkstra，换一种存储结构，复杂度能差出一个数量级。矩阵版每次挑最小点要扫一遍所有点，总共 V 轮，复杂度 O(V²)；堆优化版把「挑最小」交给优先队列，复杂度降到 O((V+E)logV)，但堆里的元素会重复入队，实际常数不小。

我做选型时一般先看点的数量级：V 在两千以内、边又比较密，矩阵版写完就能收工，没必要上堆；V 上万了还死守矩阵，那就是自己给自己找麻烦。还有一种中间情况——图很稀疏但 V 只有几百，这时候堆优化带来的常数劣势反而可能比矩阵慢，别迷信复杂度，跑一组实测数据更靠谱。

2.3 图的存储结构定义与初始化

堆优化版用的是链式前向星，比vector数组更贴近纯 C 的写法，也方便控制内存。核心是三个东西：一个边数组、一个 head 数组、一个计数器。head[u] 存的是「以 u 为起点的第一条边」在边数组里的下标，每条边再存一个 next 指向同起点的下一条边，形成一个链表。

#include <stdio.h> #include <string.h> #define MAXN 100005 /* 点数上限，按题目给的范围改，别吝啬 */ #define MAXM 400005 /* 边数上限，无向图要乘 2 */ #define INF 0x3f3f3f3f /* 约 1.06e9，两倍相加仍在 int 范围内 */ typedef struct { int to; /* 这条边指向哪个点 */ int w; /* 边权 */ int next; /* 同起点的下一条边的下标，-1 表示没有 */ } Edge; Edge e[MAXM]; int head[MAXN]; int ecnt = 0; /* 加一条 u -> v、权重 w 的有向边 */ void add_edge(int u, int v, int w) { e[ecnt].to = v; e[ecnt].w = w; e[ecnt].next = head[u]; head[u] = ecnt++; } int main(void) { /* 关键：head 必须全部置 -1，0 是合法下标，不能当空指针用 */ memset(head, -1, sizeof(head)); /* 读入与建图…… */ return 0; }

这段代码里有两处参数值得多说一句。MAXN和MAXM要按题面范围开，无向图每条输入边要调两次add_edge，所以MAXM至少是输入边数的两倍，开小了就是数组越界，越界之后程序未必立刻崩，可能只是某个点的距离莫名其妙变短，这种问题最难查。

memset(head, -1, sizeof(head))里的 -1 也是有讲究的：它把每个 int 的四个字节都填成 0xFF，在补码下正好等于 -1，所以判断「还有没有下一条边」时写i != -1就对了。如果图省事用了 0 做空值，那第 0 条边永远遍历不到，第一条边会凭空消失。

提示：sizeof(head)只在 head 是数组时才是整个数组的大小，一旦把数组传进函数退化成指针，sizeof 就只剩 8 字节，该用MAXN * sizeof(int)显式写清楚。

3. 从朴素版到手写堆：三份能直接编译的 C 实现

3.1 朴素 O(V²)：稠密图下的稳妥写法

矩阵版是理解算法最快的路径，也是机试里最不容易写错的版本。它的逻辑非常直接：每轮线性扫描找未确定点里 dist 最小的，标记它，然后扫一遍它的所有邻居做松弛。

#include <stdio.h> #include <string.h> #define MAXN 1005 #define INF 0x3f3f3f3f int g[MAXN][MAXN]; /* g[u][v] = u 到 v 的边权，无边则保持 INF */ int dist[MAXN]; int used[MAXN]; /* n 个点、编号 0..n-1，源点 s；结果留在 dist 数组里 */ void dijkstra_matrix(int n, int s) { memset(used, 0, sizeof(used)); for (int i = 0; i < n; i++) dist[i] = INF; dist[s] = 0; for (int round = 0; round < n; round++) { int u = -1; for (int i = 0; i < n; i++) { if (!used[i] && (u == -1 || dist[i] < dist[u])) u = i; } /* 剩下的点全部不可达，后面的轮次没有意义，直接退出 */ if (u == -1 || dist[u] == INF) break; used[u] = 1; for (int v = 0; v < n; v++) { if (g[u][v] == INF) continue; if (dist[v] > dist[u] + g[u][v]) { dist[v] = dist[u] + g[u][v]; } } } }

这段的逻辑主干在两层循环：外层固定跑 n 轮，内层第一次扫描负责「选点」，第二次扫描负责「松弛」。u == -1那个判断处理的是孤立点的情况——如果一个点从源点根本走不到，它的 dist 始终是 INF，扫描时可能一个合法点都挑不出来，此时dist[u]会越界访问，所以必须在前面拦住。

dist[u] == INF是提前退出的优化：一旦最小候选值都是无穷大，说明剩余点全部不可达，再跑下去只是空转。这个判断放在大图上能省掉相当一部分时间，尤其是图被切成好几个连通块的时候。

矩阵初始化有一个容易忽略的点：g是全局数组，默认全是 0，而 0 在最短路径里代表「边权为零的边」，不是「没有边」。所以读入边之前必须把整个矩阵刷成 INF，再按输入覆盖。

3.2 链式前向星加手写二叉堆：稀疏图的主力实现

堆优化版把「选最小」这一步从线性扫描换成小根堆，其余逻辑不变。C 语言里没有现成的优先队列，要么手写，要么用qsort之类的思路绕，我一般直接手写一个存(点编号, 当前距离)的二叉堆，二十行搞定。

typedef struct { int v, d; } Node; Node heap[MAXM * 2]; /* 每个点可能被多次入堆，容量按边数留余量 */ int hn = 0; void push(int v, int d) { int i = ++hn; heap[i].v = v; heap[i].d = d; while (i > 1 && heap[i / 2].d > heap[i].d) { Node t = heap[i]; heap[i] = heap[i / 2]; heap[i / 2] = t; i >>= 1; } } Node pop(void) { Node top = heap[1]; heap[1] = heap[hn--]; int i = 1; for (;;) { int l = i << 1, r = l | 1, m = i; if (l <= hn && heap[l].d < heap[m].d) m = l; if (r <= hn && heap[r].d < heap[m].d) m = r; if (m == i) break; Node t = heap[i]; heap[i] = heap[m]; heap[m] = t; i = m; } return top; }

push是上浮：新元素放到数组末尾，然后不断和父节点比较，比父节点小就交换，直到满足堆序。pop是下沉：把堆顶记下来，用最后一个元素补到堆顶，然后和两个子节点里较小的那个交换，一路沉到底。两个函数的边界都是hn，下标从 1 开始，这样i/2和i*2的父子关系才是对的；如果从 0 开始，父节点公式要改成(i-1)/2，是最容易写错的地方之一。

堆里存的是「某个时刻的 dist 快照」，同一个点可能因为被多次松弛而多次入堆。所以主循环里必须有一个done数组，弹出堆顶时先看这个点是否已经确定过，确定过就直接丢弃，这就是所谓的「懒删除」。

int dist[MAXN], done[MAXN]; void dijkstra_heap(int n, int s) { for (int i = 1; i <= n; i++) { dist[i] = INF; done[i] = 0; } dist[s] = 0; hn = 0; push(s, 0); while (hn > 0) { Node cur = pop(); int u = cur.v; if (done[u]) continue; /* 过期快照，丢掉 */ done[u] = 1; for (int i = head[u]; i != -1; i = e[i].next) { int v = e[i].to, w = e[i].w; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; push(v, dist[v]); } } } }

if (done[u]) continue;这一行是整个堆优化版本里最不能省的一行。省掉它，算法依然能跑出正确答案，但每个点会被反复展开，复杂度退化，在稠密图上甚至比矩阵版还慢。这种「结果对、性能错」的问题最难被发现，因为样例永远过得去。

3.3 编译、输入格式与结果对照

三份代码建议放在同一个目录下，用同一份输入验证结果一致性。约定输入格式为：第一行n m s（点数、边数、源点），随后 m 行每行u v w。下面是完整的主函数骨架：

int main(void) { int n, m, s; if (scanf("%d %d %d", &n, &m, &s) != 3) return 0; memset(head, -1, sizeof(head)); for (int i = 0; i < m; i++) { int u, v, w; scanf("%d %d %d", &u, &v, &w); add_edge(u, v, w); add_edge(v, u, w); /* 无向图补反向边；有向图删掉这行 */ } dijkstra_heap(n, s); for (int i = 1; i <= n; i++) { if (dist[i] == INF) printf("INF\n"); else printf("%d\n", dist[i]); } return 0; }

编译命令用gcc -O2 -Wall -o dij dijkstra_heap.c，-Wall别省，它能提前告诉你哪些变量没初始化、哪些比较是拿有符号和无符号在比。-O2在跑大数据的时候差别很明显，尤其是手写堆这种循环密集的代码。

输入约定里最需要统一的是下标基准：scanf读进来的点号是 1 到 n，所以head、dist、done全部按MAXN开并且从 1 开始用，0 号位空着不用。矩阵版如果要复用同一份输入，得在读入时统一减一，两套代码混着测的时候这里特别容易翻车。

对照结果时不要只看最后一个点。我一般会写个脚本把两份输出逐行 diff，只要有一行不一样就说明某条松弛路径走岔了，比肉眼看快得多。

4. 参数与边界：INF 取值、负权、重边和不连通

4.1 无穷大的取值与加法溢出

INF 取多少，是这套代码里最容易被轻视的参数。取0x7fffffff（int 最大值 2147483647）看起来最「无穷」，但松弛时要做dist[u] + w，两个接近上限的数一加就溢出成负数，负距离会污染整个 dist 数组，最后输出一堆莫名其妙的小值。

常见做法是用0x3f3f3f3f，约 1.06e9，它的好处是两个相加约 2.1e9，刚好卡在 int 上限内不溢出；同时它足够大，只要真实路径长度不超过 1e9 就不会误判。如果边权可能到 1e9 级别、路径又要累加很多条，那就得换long long，INF 相应改成0x3f3f3f3f3f3f3f3fLL。

还有一个隐蔽点：松弛条件写成dist[v] > dist[u] + w时，如果dist[u]本身就是 INF，加法会先发生再比较，虽然0x3f3f3f3f两倍不溢出，但结果依然是个巨大的数，比较一定能过、不会误更新。用0x7fffffff就没这个运气了。所以在松弛前加一句if (dist[u] == INF) continue;是最稳的写法，代价可以忽略。

4.2 负权边、自环、重边与有向无向

负权边前面已经说过，Dijkstra 处理不了，读入时扫一遍直接拒绝，比跑完再怀疑人生强。自环（u 到自己）不会影响正确性，但在无权图里可能造成死循环式的无效松弛，加边时判断if (u == v) continue;顺手跳过更干净。

重边是另一个高频场景：同一对点之间给了多条边。矩阵版天然处理得好——读入时取min就行，后到的边如果更大就覆盖掉；链式前向星版会把多条边都存进去，算法照样能跑对，因为松弛时会自动选小的那条，只是白白多占内存、多几次无效遍历。如果边数很紧张，读入时用哈希或者排序去重也可以，但大多数题目不值得这么做。

有向和无向的区别只在一个地方：加边时调不调反向的那次add_edge。这个开关如果搞错，有向图当无向图跑会多出根本不存在的最短路，无向图当有向图跑则会漏掉一半路径，而且两种错法在小样例上未必暴露。

注意：无向图的MAXM必须是输入边数的两倍，否则边数一多就数组越界，而越界写坏的很可能是相邻的head数组，症状是某些点突然变得「不可达」。

4.3 不连通图、多组数据与数组清理

不连通图在输出阶段要单独处理。dist[i] == INF的点表示从源点无法到达，输出时按题面要求写-1或者INF，别直接打印那个 1061109567，看起来像是算错了。

多组测试数据是另一个坑。head、ecnt、hn、done这几个全局状态每组都要重置，ecnt = 0和memset(head, -1, ...)必须写在每组读入之前。漏掉ecnt重置，边会一组一组往后堆，第二组开始读到的就是上一组的残留边，结果时对时错，非常玄学。

内存估算也值得在动手前做一遍。矩阵版 V=5000 时是 25e6 个 int，约 100 MB，很多在线评测的内存上限直接卡死；V=1000 时只有 4 MB，随便跑。堆优化版的空间是(V + 2E) * 12字节左右，E=2e5 时不到 5 MB，压力小得多。选型之前先算这笔账，比写完再改省时间。

5. 避坑排查：五个把结果算错的细节

5.1 样例全过、大样例错：INF 相加溢出

现象：小数据结果和暴力对得上，数据量一大就出现负数距离或者明显偏小的值。

原因：INF 用了0x7fffffff，松弛时dist[u] + w溢出成负数，比较条件被这个负数骗过去，dist[v]被更新成一个负值，之后沿着负值继续传播。

解决：INF 换成0x3f3f3f3f，并在松弛前加if (dist[u] == INF) continue;。如果边权量级大，整体切到long long，不要试图用 int 硬撑。

5.2 堆里的点被重复处理

现象：结果正确，但大图上明显超时，和预期复杂度对不上。

原因：手写堆没有done判重，同一个点因为多次松弛被多次入堆，每次弹出都重新扫一遍它的邻接表，复杂度退化到接近 O(V·E)。

解决：主循环弹出后先if (done[u]) continue;，确定过的点直接丢弃。同时检查push的调用位置，只在松弛成功时入堆，别在每轮无条件入堆。

5.3 距离相等时路径还原跑偏

现象：距离值全对，但输出的路径节点顺序和预期不一致，极端情况下路径里出现环。

原因：松弛条件写成了dist[v] >= dist[u] + w，距离相等时也更新pre[v]，在零权边或者多条等长路径上，前驱指针互相指向，最后还原时就成环了。

解决：条件必须是严格大于>。如果业务上要求「距离相同取字典序更小的路径」，那就单独写一套比较逻辑，不要靠改这个符号来实现。

5.4 下标从 0 开始还是 1 开始

现象：某个点的距离总是差一条边，或者第一个点的结果永远不对。

原因：矩阵版按 0..n-1 写，堆优化版按 1..n 写，两份代码共用同一份输入时没有统一转换；或者输入是 1-based，代码里却直接拿去索引 0-based 的数组。

解决：全篇统一一种基准，我一般选 1-based，因为题面基本都这么给；矩阵版内部要用 0-based 的话，在读入处统一减一，并且注释写清楚。别在算法中间混着来。

5.5 多组数据不清理导致第二组开始错

现象：第一组数据输出正确，第二组开始结果乱七八糟，而且错得没有规律。

原因：ecnt、hn没有在每组开始时清零，边表和堆里残留着上一组的数据；或者memset只清了dist忘了清done。

解决：把每组的初始化收成一个函数init(n)，里面把ecnt、hn置零，head刷 -1，dist刷 INF，done刷 0，主函数里每组开头调一次，不给自己漏的机会。

6. 进阶：路径还原、多源扩展与对拍验证

距离算出来只是第一步，真正交付时基本都要输出具体走法。路径还原靠一个pre数组，松弛成功时记下前驱，最后从终点往源点倒推，再反转一次。关键是pre的初始化：源点的pre[s] = -1作为终止标记，其余点初始化为 -1 或者 0 都行，但倒推循环必须靠s停下来，不能靠「pre 等于 0」判断，因为 0 可能是合法点号。

int pre[MAXN]; /* 松弛成功时同步更新前驱 */ if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; pre[v] = u; push(v, dist[v]); } /* 从终点 t 倒推回源点 s，路径存在 path 里 */ int path[MAXN], len = 0; for (int cur = t; cur != -1; cur = pre[cur]) { path[len++] = cur; if (len > n) { /* 成环保护，正常不该走到这里 */ break; } } /* path[0..len-1] 是逆序，倒着打印即可 */ for (int i = len - 1; i >= 0; i--) printf("%d%c", path[i], i ? ' ' : '\n');

len > n那个保护不是多余的。只要松弛条件写成>=，或者图里存在零权环，倒推就可能绕不出来，加一行判断能把死循环变成一次明确报错，调试时省很多时间。

多源场景稍微改一下就行：把多个源点全部以dist = 0入堆，跑一次就得到「任意源点到各点的最近距离」，语义上等价于加了一个超级源点。多终点更简单，距离全算完，取需要的那几个点即可，不需要每个终点单独跑一遍。

最后一件事是验证。我现在的习惯是写完先不碰大数据，直接上对拍：写一个十行左右的 Floyd 暴力版本，在小规模随机图上和 Dijkstra 逐组比对。生成器控制点数在 8 以内、边权在 1 到 20 之间，跑三百组，只要有一组不一样就立刻停下来看输入。

#!/usr/bin/env bash # 对拍：小图用 Floyd 校验 Dijkstra 的正确性 gcc -O2 -Wall -o dij dijkstra_heap.c || exit 1 for i in $(seq 1 300); do python3 gen.py > in.txt # 随机生成小图 ./dij < in.txt > out1.txt python3 brute_floyd.py < in.txt > out2.txt if ! diff -q out1.txt out2.txt > /dev/null; then echo "第 $i 组不一致，输入如下：" cat in.txt break fi done

这套流程抓出过好几次「样例过、边界错」的问题，最典型的一次是重边取最小值没处理，正好被随机数据撞上。对拍的价值在于它不挑场景，而人手造的样例永远只覆盖自己想到的那几种情况。从那以后我每次写最短路相关的代码，都强制先跑一遍三百组对拍再去看大数据性能，宁可多花十分钟，也不想在深夜对着一份「看起来对」的输出反复怀疑自己。希望帮到你。

本文还有配套的精品资源，点击获取