简介：围绕最短路径 Dijkstra 算法展开的 C 语言课程设计资料，面向正在学习数据结构与图算法、需要完成单源最短路径实验或课程设计的高校学生及入门开发者。压缩包共 2 个文件，以 cpp 源码和 doc 文档为主，整体约 139KB；其中源码对应图的结构定义、存储方式与 Dijkstra 求解流程，文档则可用于梳理设计思路、实验组织、结果分析和报告撰写。已有 11696 人学习下载，具备较好的参考与借鉴价值。读者可在 VC++6.0 环境中对照完成图的创建与单源点最短路径计算，理解结构体、指针等基础知识在算法程序中的组织方式，并借助源码调试和文档说明查漏补缺；相关思路还可迁移到交通旅游、城市规划、电网架设等路径选择场景，适合用作课程设计参考和算法复盘材料。

1. 最短路径 Dijkstra 的C语言落地：从一张邻接矩阵到能跑的求解器

最短路径 Dijkstra 在 C 语言课程设计和笔试题里出现频率极高，但网上流传的版本里，能直接编译、能处理重边、能打印完整路径的并不多。不少人拿到的是一份只输出距离、不带前驱数组的半成品，题目一要求输出路径就得回头重写。这里拆的是一份完整的 C 语言实现，包含邻接矩阵的 O(V²) 朴素版、链式前向星加二叉堆的 O((V+E)logV) 优化版，以及路径回溯和一组边界用例。适合两类人：正在做课程设计、需要一份能跑通也能讲清原理的代码；以及写过最短路、被 INF 溢出和顶点编号绊过的朋友。它解决的不是「知道 Dijkstra 是什么」，而是「拿到一份改几行就能用的实现」。

2. 图怎么装进内存：邻接矩阵与链式前向星的开销账本

动手写算法之前，先要把图的存储定下来。这一步选错，后面堆优化、路径回溯、重边处理全都要跟着改。C 语言没有标准容器，也没有 vector 和优先队列，所有结构都得自己用静态数组或 malloc 手工搭，所以选型比 Python 那边更值得较真。

2.1 两种存储结构的成本对照

邻接矩阵的本质是一个 V×V 的二维数组，g[u][v]直接给出边权，判边存在是 O(1)，松弛时遍历 u 的所有邻居是 O(V)。链式前向星用一个head数组加若干条边结构体，把所有出边串成链表，遍历邻居是 O(deg(u))，判边存在则要顺着链走。

稠密图用矩阵更省事，稀疏图必须换链式前向星。我一般会看边数：如果 E 接近 V²，矩阵的 O(V²) 主循环本来就要跑满，多占的空间不亏；如果 E 只有几倍 V，那矩阵里绝大多数格子都是 INF，纯属浪费缓存。

2.2 用静态数组把图的边界钉死

课程设计里我倾向于用文件作用域的静态数组，避免 malloc 失败还要处理返回值。缺点是不能同时开多个图，但单次求解的场景够用。核心结构只有三个：边权矩阵、距离数组、前驱数组。

#include <stdio.h> #include <string.h> #define MAXV 1005 #define INF 0x3f3f3f3f static int g[MAXV][MAXV]; /* g[u][v] 存边权，无边为 INF */ static int dist[MAXV]; /* 源点到各点的当前最短距离 */ static int prev[MAXV]; /* 前驱顶点，路径回溯用，-1 表示无 */ static int visited[MAXV]; /* 是否已确定最终最短路 */ void graph_init(int n) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { g[i][j] = (i == j) ? 0 : INF; } } }

INF这里取0x3f3f3f3f（约 1.06×10⁹），不是INT_MAX。原因在避坑章节会细说：两个 INF 相加不能溢出成负数，0x3f3f3f3f 的两倍约 2.1×10⁹，仍在 int 范围内。对角线初始化为 0 表示自己到自己的距离为零，这一点在松弛时能让「源点绕一圈回到自己」的边被自然忽略。

MAXV开 1005 是给 1-based 输入留的余量。如果确定输入从 0 开始，开到 n 就够。static修饰让数组落在静态区，不会因为栈帧过大导致运行时崩溃。

2.3 读入边的写法与重边合并

输入解析这一步最容易埋雷。题目给的顶点编号可能是 1 到 n，代码里却按 0 到 n-1 建图；同一对顶点可能给多条边；无向图需要正反各插一次。这些都要在读入阶段处理干净。

int main(void) { int n, m, src; if (scanf("%d %d %d", &n, &m, &src) != 3) return 1; graph_init(n); for (int i = 0; i < m; i++) { int u, v, w; if (scanf("%d %d %d", &u, &v, &w) != 3) return 1; /* 若输入为 1-based，这里统一减 1 */ u -= 1; v -= 1; if (w < g[u][v]) { g[u][v] = w; /* 重边只保留最小的一条 */ } /* 无向图追加一行：g[v][u] = g[u][v]; */ } dijkstra(n, src - 1); /* 源点同样减 1 */ return 0; }

关键点有三个。第一，编号统一在读入处转换，不要在算法内部混用 0-based 和 1-based，那是后面所有数组越界的根源。第二，重边用if (w < g[u][v])合并，题目给两条 3 和 5 的边时，只有较小的那条会影响结果。第三，无向图的正反插入要么在循环内对称写两行，要么封装成add_edge函数调用两次，不要在算法里区分方向。

scanf的返回值判断别省。真实评测数据里偶发有多余空行或格式错误，不做检查会读到未初始化的变量，最后得到一个看似合理其实随机的答案，排查成本极高。

3. 朴素 Dijkstra 的C实现：三个数组、一个主循环、一次回溯

数据结构定好之后，算法主体其实不长，二三十行就能写完。真正需要讲清楚的是每个数组在循环里的状态变化，以及为什么这样写是对的。很多人能默写这段代码，但被问到「u 为什么可以提前 break」「visited 到底防的是什么」时会卡住。

3.1 dist / prev / visited 的分工

三个数组各管一件事，职责不能混。

dist[i]记录的是「从源点出发、只经过已经确定最短路的顶点、到达 i 的当前最优距离」。它初始化时除了源点为 0，其余全是 INF，随着松弛不断变小，最终收敛到真正的最短路。注意它在中途不是最终答案，只是一个上界。

visited[i]是一个布尔标记，表示 i 是否已经「出圈」——也就是它的 dist 值已经可以被证明不会再变小。Dijkstra 的贪心正确性就建立在这个标记上：每轮从所有未标记顶点里挑 dist 最小的那个，标记它，然后用它去松弛邻居。

prev[i]存的是 i 在最短路径上的前一个顶点，初值 -1。它只在松弛成功的那一瞬间被更新，也就是dist[v]被改小时，prev[v] = u。这个数组本身不参与距离计算，纯粹是为了最后回溯路径。

写成表更直观：

3.2 选点与松弛：主循环逐行拆

void dijkstra(int n, int src) { for (int i = 0; i < n; i++) { dist[i] = INF; prev[i] = -1; visited[i] = 0; } dist[src] = 0; for (int round = 0; round < n; round++) { /* 第一步：在未访问顶点中选出 dist 最小的 */ int u = -1; int best = INF; for (int i = 0; i < n; i++) { if (!visited[i] && dist[i] < best) { best = dist[i]; u = i; } } if (u == -1) break; /* 剩下的点全不可达，提前收工 */ visited[u] = 1; /* 第二步：用 u 去松弛它的所有邻居 */ for (int v = 0; v < n; v++) { if (g[u][v] == INF) continue; long long cand = (long long)dist[u] + g[u][v]; if (cand < dist[v]) { dist[v] = (int)cand; prev[v] = u; } } } }

逐段说明。

外层round从 0 到 n-1，最多 n 轮，每轮确定一个顶点，所以循环次数是顶点数。实际运行中如果图不连通，中途u == -1就 break，剩下的顶点 dist 保持 INF，表示不可达。这个 break 不是可选项，不加的话下一轮会用 u = -1 去访问g[-1][v]，直接越界。

选点循环里dist[i] < best用严格小于。如果有两个顶点 dist 相同，先遇到的被选中，结果不受影响，因为两个都是最短距离，只是确定顺序不同。这一点在需要稳定输出的场景里可以改成<=来固定选择顺序，但那属于输出格式需求，不影响正确性。

松弛部分先判g[u][v] == INF，跳过不存在的边。然后cand用long long中转，就算dist[u]和g[u][v]都接近 INF，相加也不会溢出后变成负数。cand < dist[v]成立才更新，同时写prev[v] = u。注意这里没有判visited[v]，因为对已确定的顶点再松弛一次得到的值不可能更小，写进去也无害，只是浪费一次比较。

3.3 路径回溯与不可达顶点

距离算完，路径还得单独拼。prev数组从目标点往前跳，跳到源点为止，过程中自然形成逆序，用一个数组当栈翻过来即可。

void print_path(int src, int dst) { if (dist[dst] == INF) { printf("unreachable\n"); return; } int stack[MAXV]; int top = 0; for (int cur = dst; cur != -1; cur = prev[cur]) { stack[top++] = cur; if (cur == src) break; /* 到源点就停，避免多走一步 */ } printf("dist=%d path=", dist[dst]); while (top > 0) { printf("%d", stack[--top]); printf(top > 0 ? "->" : "\n"); } }

两个细节。第一，进入循环前先判dist[dst] == INF，不可达直接返回，否则会顺着 prev 链走到 -1，栈里塞进一个非法下标。第二，回溯循环里cur == src时主动 break。如果不 break，下一轮cur = prev[src] = -1，循环条件也会终止，看起来没问题，但当源点自己有一条自环或重边时，prev[src]可能被写成其他值，就会多走一段。主动 break 更稳妥。

当dst == src时，栈里只有源点一个元素，输出dist=0 path=0，符合预期。这一步在很多实现里会输出空行或者直接崩掉，属于边界没考虑。

4. 堆优化版本：链式前向星加二叉堆，把 O(V²) 压到 O((V+E)logV)

朴素版在 V 小的时候完全够用，代码短、好调试、不容易错。但只要顶点数上到几万，内层那个 O(V) 的选点循环就会把总时间拉到无法接受的程度。这时候需要换存储结构，再补一个优先队列。

4.1 O(V²) 在什么规模上会翻车

算一笔账。V = 1000 时，V² = 10⁶，现代机器上几十毫秒内跑完，随便用。V = 10⁴ 时，V² = 10⁸，大概一秒左右，评测机紧张一点就可能超时。V = 10⁵ 时，V² = 10¹⁰，无论怎么优化常数都救不回来。

而稀疏图的实际边数往往只有几倍 V。以 V = 10⁵、E = 2×10⁵ 为例，堆优化的复杂度是 (V+E)logV ≈ 3×10⁵ × 17 ≈ 5×10⁶，比 10¹⁰ 小了三个数量级。所以判断标准很直接：看题目给的 V 上限，超过 5000 且图不稠密，就上堆。

代价是代码复杂度上升，堆要手写，链式前向星的下标要维护，懒删除要记得判。这些都是可以一次性封装好的，写熟之后并不比朴素版多花多少时间。

4.2 链式前向星加手写二叉堆

C 没有priority_queue，标准做法是自己维护一个小根堆。下面的实现里，堆元素是(顶点编号, 当前距离)，按距离排序。

#include <stdio.h> #include <string.h> #define MAXV 100005 #define MAXE 200005 #define INF 0x3f3f3f3f typedef struct { int to; int w; int next; } Edge; static Edge edges[MAXE * 2]; static int head[MAXV]; static int edge_cnt = 0; static 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数组初值必须全部设成 -1，表示没有出边。edge_cnt从 0 开始递增，每条边占据edges的一个槽位。add_edge把新边插到链表头部，next指向原来的头，这是链式前向星的标准写法。无向图调用两次，正反各一条。

堆的部分：

typedef struct { int v; long long d; } Node; static Node heap[MAXE * 4]; static int heap_size = 0; static void heap_push(int v, long long d) { int i = heap_size++; heap[i].v = v; heap[i].d = d; while (i > 0) { int p = (i - 1) / 2; if (heap[p].d <= heap[i].d) break; Node tmp = heap[p]; heap[p] = heap[i]; heap[i] = tmp; i = p; } } static Node heap_pop(void) { Node top = heap[0]; heap[0] = heap[--heap_size]; int i = 0; while (1) { int l = 2 * i + 1; int r = 2 * i + 2; int m = i; if (l < heap_size && heap[l].d < heap[m].d) m = l; if (r < heap_size && heap[r].d < heap[m].d) m = r; if (m == i) break; Node tmp = heap[m]; heap[m] = heap[i]; heap[i] = tmp; i = m; } return top; }

堆数组开MAXE * 4而不是 V，因为懒删除策略下同一个顶点可能被反复压入，次数上限与松弛成功的次数同阶，也就是边数级别。开小了会越界，这是堆版本最常见的翻车点之一。

heap_push从尾部插入后向上冒泡，父节点下标是(i-1)/2，距离更小的往上走。heap_pop把尾元素搬到根，再向下沉，每次选左右孩子里距离更小的那个交换。两个函数都不做边界检查，因为调用方保证堆非空。

主算法：

void dijkstra_heap(int n, int src, long long *dist) { for (int i = 1; i <= n; i++) dist[i] = INF; dist[src] = 0; heap_size = 0; heap_push(src, 0); while (heap_size > 0) { Node cur = heap_pop(); /* 懒删除：弹出的距离比当前记录大，说明是过期条目 */ if (cur.d > dist[cur.v]) continue; for (int e = head[cur.v]; e != -1; e = edges[e].next) { int to = edges[e].to; long long nd = cur.d + edges[e].w; if (nd < dist[to]) { dist[to] = nd; heap_push(to, nd); } } } }

主循环里没有visited数组，取而代之的是if (cur.d > dist[cur.v]) continue;这一行。它的作用是跳过堆里那些「顶点被松弛了多次、旧条目还没弹出来」的无效记录。没有这一行，算法仍然能跑出正确答案，但会重复处理大量过期节点，性能退化得厉害。

dist数组这里用long long，因为路径长度累加后可能超过 int 范围。如果题目保证边权和顶点数都在 int 内，用 int 也行，但需要把 INF 换成0x3f3f3f3f3f3f3f3fLL。

4.3 懒删除：堆里为什么允许留旧节点

标准二叉堆不支持「修改堆中某个元素的值」，只支持插入和弹出。Dijkstra 在松弛时需要把某个顶点的距离改小，如果堆不能改值，通常有两种做法：一是额外维护位置索引实现 decrease-key，二是不管旧值，直接压入新值，弹出时再判断是否过期。这份实现用的是第二种，也就是懒删除。

懒删除的好处是实现简单，不需要在堆里维护pos数组，也不需要在交换时同步更新。代价是堆的最大容量变大，最坏情况下每个顶点入堆次数等于它的入度，总入堆次数不超过 E。所以堆数组开到MAXE * 4是安全的，留了四倍余量。

判断过期的条件是cur.d > dist[cur.v]。等号不能加，因为同一个顶点可能存在两条距离相同的记录（虽然少见），加等号会误杀，导致某些点不再被扩展。

实际运行中，懒删除带来的额外操作通常只有常数倍，比起 decrease-key 的实现复杂度和出错概率，这笔账是划算的。我在工程里更倾向于懒删除，只有在极端性能敏感的场景才会考虑手写索引堆。

5. 常见问题排查：五类翻车现场与定位手法

代码能编译不代表能过题。Dijkstra 的错误往往不是崩溃，而是答案偏大、偏小或者偶发不一致，排查起来比空指针更费劲。下面五类是我见过频率最高的，按「现象 → 原因 → 解决」整理。

5.1 负权边：算法前提被悄悄打破

现象：同一份代码，在小数据上答案正确，换一组带负权边的数据后结果比标准答案大，而且换个输入顺序答案还会变。

原因：Dijkstra 的贪心正确性依赖「边权非负」。每轮选出的 dist 最小顶点，只有在所有边权都不为负时才能保证它不会被后续路径改小。一旦存在负权边，一个已经 visited 的顶点可能被另一条经过负边的路径更新，但代码不会再处理它，于是结果停在错误的中间值。

解决：先确认题目边权范围，明确写了「非负」才用 Dijkstra。有负权时改用 Bellman-Ford，复杂度 O(VE)，V 小的时候能接受；或者用 SPFA，但要意识到它在特定构造下会退化。不要试图在 Dijkstra 里打补丁，改出来的东西既不是 Dijkstra 也没有正确性保证。

5.2 INF 溢出：两个无穷相加变成负数

现象：某些不可达顶点的 dist 打印出来是一个很小的负数，或者松弛过程中出现「距离越走越短」的诡异现象。

原因：INF 用了INT_MAX（2147483647），dist[u] + g[u][v]在 u 不可达时变成INT_MAX + w，signed 溢出是未定义行为，实际机器上通常回绕成负数。负数和dist[v]比较当然更小，于是被写进去，污染整张图。

解决：INF 取0x3f3f3f3f，两倍约 2.1×10⁹，仍在 int 范围内，即使两个 INF 相加也不会溢出成负。如果路径总和可能超过 10⁹，整体换成long long，INF 同步改成0x3f3f3f3f3f3f3f3fLL。另外在松弛前先判dist[u] != INF，双重保险。

5.3 顶点编号与重边：一份输入三种答案

现象：样例过，提交挂；或者本地跑出来路径里出现了 0 号顶点，而题目顶点是从 1 开始的。

原因：输入 1-based，代码按 0-based 建图，源点没减一或者边端点只减了一边。另一种情况是重边没合并，矩阵里后写入的边覆盖了先写入的较小边。

解决：在main读入处统一减一，算法内部只认 0-based，不要在两处混着转。重边用if (w < g[u][v])取最小，无向图正反都要判。写完后拿一个 n=1、m=0 的输入测一下，看会不会越界，这是最快的编号自检。

5.4 堆版本不判旧节点：内存和时间的双重浪费

现象：堆优化版本在 10⁵ 规模的数据上跑到好几秒，甚至堆数组越界导致段错误。

原因：懒删除的过期条目没有跳过，同一个顶点被反复扩展，入堆次数远超预期。堆数组按 V 开而不是按 E 开，插入次数一多就写穿。

解决：heap_pop之后立刻加if (cur.d > dist[cur.v]) continue;。堆容量按MAXE * 2或MAXE * 4开，不要图省内存按 V 开。如果内存实在紧张，可以改成索引堆加 decrease-key，但代码量会翻倍。

5.5 路径回溯死循环：prev 数组的初值

现象：打印路径时程序卡住不返回，或者输出一长串重复顶点后崩溃。

原因：prev数组初始化时用了 0 而不是 -1，回溯循环以cur != 0作为终止条件，遇到真正的 0 号顶点就停不下来；或者某个顶点的prev被错误地写成它自己。

解决：prev全部初始化为 -1，回溯条件写成cur != -1，并在cur == src时主动 break。写完回溯函数后单独拿源点等于目标点的输入测一次，确认输出是单点而不是死循环。

6. 用对拍和边界用例给实现上保险

堆版本写完之后，我一般不会直接拿去提交，而是先花十分钟做两件事：写一个暴力版本对拍，再手造三个边界输入。这两步能拦下绝大多数低级错误，比盯着代码看有效得多。

6.1 用 Bellman-Ford 做随机对拍

Bellman-Ford 慢，但逻辑简单、几乎不会写错，是天然的对拍基准。生成随机小图，分别跑两份实现，比较 dist 数组的每一位。

#include <stdio.h> #include <stdlib.h> #include <string.h> #define N 8 #define INF 0x3f3f3f3f static int g[N][N]; static int bellman(int n, int src, int dst) { int d[N]; for (int i = 0; i < n; i++) d[i] = INF; d[src] = 0; for (int k = 0; k < n - 1; k++) { for (int u = 0; u < n; u++) { if (d[u] == INF) continue; for (int v = 0; v < n; v++) { if (g[u][v] == INF) continue; if (d[u] + g[u][v] < d[v]) d[v] = d[u] + g[u][v]; } } } return d[dst]; } int main(void) { srand(12345); for (int iter = 0; iter < 200; iter++) { int n = 2 + rand() % (N - 2); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) g[i][j] = (i == j) ? 0 : INF; for (int u = 0; u < n; u++) { for (int v = 0; v < n; v++) { if (u != v && rand() % 100 < 40) { g[u][v] = 1 + rand() % 20; /* 只生成正权 */ } } } dijkstra(n, 0); for (int v = 0; v < n; v++) { int expect = bellman(n, 0, v); if (dist[v] != expect) { printf("mismatch iter=%d v=%d got=%d expect=%d\n", iter, v, dist[v], expect); return 1; } } } printf("all passed\n"); return 0; }

这段代码里dijkstra用的是前面第 3 章的矩阵版，直接复用即可。rand() % 100 < 40控制边密度在 40% 左右，保证图不至于太稀疏。权值取 1 到 20 的正整数，因为对拍的前提是两份实现都只处理非负权。

跑通 200 组随机图，基本可以确认主体逻辑没问题。如果第一组就 mismatch，先把 n 固定成 4 打印中间过程，看是哪一轮松弛出的偏差。

6.2 三个必须手造的边界输入

随机对拍覆盖不到结构性边界，下面三个输入要单独测。

单点图专门测prev初值和回溯终止条件，不连通图测u == -1的 break 和 INF 输出，重边测读入阶段的合并逻辑。这三个用例加起来不到二十行输入，但每次改完代码我都会重新跑一遍。

从那以后我每次写完最短路，都强制走一遍「对拍 + 三个边界」的流程，宁可多花十分钟，也不想在评测机上对着一个偏大 1 的答案反复怀疑人生。希望帮到你。

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