简介一份面向数据结构学习者与算法初学者的最短路径课程设计实现基于 C 语言与 VC6.0 环境完整演示了图的创建与存储、单源点最短路径求解的核心流程。压缩包内共 2 个文件分别为可直接运行的 CPP 源程序与 DOC 设计文档便于对照代码与原理说明资源包体积仅 139KB轻量易用。其中 CPP 源码包含完整注释并采用结构体与指针实现图的邻接矩阵存储适合对照算法步骤逐步调试DOC 文档则涵盖问题分析、设计思路与测试结果可作为课程设计报告模板参考。目前已有 11694 人学习浏览对理解图算法与 C 语言实践有较高参考价值。读者可从中掌握图的定义与存储方法、迪杰斯特拉算法的编码技巧并可将最短路径模型迁移到交通旅游、城市规划、电网架设等实际场景。文档与源码配套结构精简适合完成课程设计、期末复习或自学数据结构时使用。1. 最短路径 Dijkstra 算法 C 语言实现一张图、一个数组、一段不难的循环当你需要在 C 语言里求单源最短路径Dijkstra 算法几乎是第一个被搬上桌的方案它不依赖数据库不需要第三方库甚至不需要递归只要一张图、一个距离数组和一个循环就能从指定起点算出到其它所有顶点的最短距离。我见过很多人把伪代码背得滚瓜烂熟真到键盘前却卡在初始化也见过某些课程设计里直接用别家框架结果连“边权为 0”和“没有边”都分不清。这篇围绕「最短路径 Dijkstra算法C语言实现」展开从图怎么存、循环怎么写、堆怎么优化到哪些地方最容易翻车给你一份可以直接照着改的 C 代码。新手能跟着步骤跑通熟手也能从参数边界和坑位里拿走点实在东西。2. 先用邻接矩阵把图装进 CDijkstra 的适用边界与初始化细节很多教程把 Dijkstra 讲成抽象的“松弛操作”可落到 C 语言第一步永远是数据结构。你选的图结构会决定后面每一个 for 怎么写也会决定这个程序能扛住多大规模的输入。2.1 邻接矩阵还是邻接表拿稀疏度做选择题常见做法是顶点数量在 1000 左右、边比较稠密时直接用二维数组做邻接矩阵顶点上万、边特别少时再用邻接表。我一般会先按最坏情况估算内存n * n个 intn 为 1000 时约 4MB课程设计和本地工具都能接受n 到 5000 就要 100MB这时候矩阵方案基本可以放弃了。邻接表省空间但实现多一级结构体还要维护边链表的插入新手容易写出野指针。下面是我常用的“静态邻接矩阵 结构体上下文”定义#define MAXN 1005 #define INF 0x3f3f3f3f typedef struct { int n; int w[MAXN][MAXN]; // w[i][j] 边权, -1 表示没有边 } Graph; typedef struct { int dist[MAXN]; int visited[MAXN]; int pre[MAXN]; // pre[v] 最短路径中 v 的前一个顶点 } DijkstraResult; void graph_init(Graph* g, int n) { g-n n; for (int i 0; i n; i) for (int j 0; j n; j) g-w[i][j] -1; // 用 -1 表示无边而不是 0 }用-1表示无边是为了区分“两个顶点之间没有路”和“边权为 0 的路径”。如果边权允许为 0而又拿 0 当无边标记初始化时所有顶点都像被一条 0 权边直接连起来dist 数组会全部变成 0算法在开始前就已经错了。INF取0x3f3f3f3f是经典习惯它约等于 10.6 亿两个这样的值相加也不会超过 int 上限方便后面做加法比较。2.2 非负权是硬门槛为什么负权会让贪心失效Dijkstra 的核心逻辑是每轮从“未访问”集合里挑一个 dist 最小的顶点认定它已经拿到最终最短距离再用它去松弛邻居。这个“挑出来就不回头”的做法成立的前提是图中所有边权非负。非负权保证任何绕路都不可能让当前最小值变得更小一旦存在负权边一个顶点完全可能在后面通过那条负边把距离刷得更低但 Dijkstra 已经把它锁死不会给它第二次机会。现象就是程序不报错、不崩溃答案却静默地错掉而且只在某些特定图结构下出错排查起来非常难受。遇到负权图正确做法不是给 Dijkstra 打补丁而是换 Bellman-Ford 或 SPFA。判断一个场景该不该用 Dijkstra先问一句边权允许负数吗允许就直接排除。2.3 三张数组撑起整个算法dist、visited、path 的定义与初始化真正决定 Dijkstra 实现风格的是三个数组dist 记录当前已知最短距离visited 标记顶点是否已被确认pre 记录最短路径上的前驱。初始化时dist 除起点外全部填 INFvisited 全部置 0pre 全部置 -1。这里有个细节起点自身要不要在进入循环前就标记 visited标准做法是先不标记让第一轮循环把起点选出来再在松弛时自然处理。如果急着把visited[src]置 1后续在多起点逻辑或堆优化版本里容易画蛇添足。void dijkstra_init(DijkstraResult* res, int src) { for (int i 0; i MAXN; i) { res-dist[i] INF; res-visited[i] 0; res-pre[i] -1; } res-dist[src] 0; }这种写法的好处是把“初始化”和“算法主循环”拆开测试时能反复重置不必重建整张图。参数 src 是起点编号约定顶点编号从 0 到 n-1。如果你的输入是 1 到 n就在读边的同时统一减 1不要在算法内部坐地起价地做映射。pre 初始化成 -1 也很关键如果初始化成 0路径回溯时会把 0 当成所有顶点的前驱打印出来的路径先跳到一个无关顶点非常误导。3. 基础版 C 代码O(n²) 的 Dijkstra 怎么一步步写完这一章把最朴素、最不容易藏 bug 的 O(n²) 版本写完整。它适合 n 在 1000 左右、以理解算法主干为目的的场景也适合作为后面堆优化版的对照组。3.1 完整函数把「每次找最小未访问点」落成循环void dijkstra(Graph* g, DijkstraResult* res, int src) { dijkstra_init(res, src); for (int round 0; round g-n; round) { int u -1; int best INF; // 第一层从未访问顶点里选出 dist 最小的 for (int i 0; i g-n; i) { if (!res-visited[i] res-dist[i] best) { best res-dist[i]; u i; } } if (u -1) break; // 剩余的未访问点全都不可达 res-visited[u] 1; // 第二层用 u 去松弛它的邻居 for (int v 0; v g-n; v) { if (g-w[u][v] ! -1 !res-visited[v] res-dist[u] g-w[u][v] res-dist[v]) { res-dist[v] res-dist[u] g-w[u][v]; res-pre[v] u; } } } }外层循环round最多执行 n 次因为每轮至少能确认一个顶点。u -1的提前退出很重要当剩余顶点都不可达时继续找最小值也是 INF白白浪费一轮。内层两个 for 都扫描所有顶点这就是 O(n²) 的来源。3.2 逐段拆解INF、两个 for、一次松弛更新第一个 for 做的事情是“扫描 选择”每次从所有未访问顶点里挑出 dist 最小者。best变量保存当前这一轮的最小值u保存对应的顶点编号。如果某个顶点 dist 是 INF说明它到起点还没有路不可能在这一轮被选中。选中 u 之后立刻把visited[u]置 1意思是“u 的最短距离已经确认后续不需要再回头改”。第二个 for 遍历所有 v检查三条条件u 到 v 有边、v 还没被确认、从 u 绕过去更短。三条都满足就更新 dist[v]同时更新 pre[v] 为 u。三个参数里Graph*负责提供边权DijkstraResult*负责收纳结果src是起点。为什么不把 dist、visited、pre 全部写成全局数组因为写成结构体指针后函数可以重复调用测试多组起点时不用手动清全局变量。如果你图省事用全局数组记得每次调用前都要重新初始化一遍否则上一组数据会污染下一组。3.3 用一个小图跑通 main输入格式与输出对照#include stdio.h int main(void) { Graph g; DijkstraResult res; int n, m; if (scanf(%d %d, n, m) ! 2) return 1; graph_init(g, n); for (int k 0; k m; k) { int u, v, w; if (scanf(%d %d %d, u, v, w) ! 3) return 1; g.w[u][v] w; // 有向图只写这一行无向图再补 g.w[v][u] w; } dijkstra(g, res, 0); for (int i 0; i n; i) { printf(dist[%d] %d\n, i, res.dist[i]); } return 0; }用下面这张有向图测试起点是 05 7 0 1 10 0 3 5 1 2 1 1 3 2 2 4 4 3 1 3 3 2 9预期输出应该包含dist[0]0、dist[1]8、dist[2]9、dist[3]5、dist[4]13。注意0 - 3 - 1的 8 比0 - 1的 10 短这才体现松弛的意义。如果跑出来不对先检查读边是否有向、有没有把scanf失败当正常流程继续。4. 堆优化版本与路径还原从 O(n²) 到 O(mlogn) 的常见做法当 n 到万级O(n²) 就扛不住了。常见做法是用优先队列维护“当前最小的未访问点”把每轮找最小值的 O(n) 摊到每次松弛的 O(logn) 上。C 语言没有现成的 priority_queue我一般会手写一个小顶堆而不是引入额外依赖。4.1 手写小顶堆而不是调库可控的回溯数组小顶堆里每个元素保存两个信息顶点编号和对应的 dist 值。堆按 dist 值排序这样每次 pop 出来的就是当前最小的候选顶点。先写堆的插入#define HEAP_MAX 2000005 typedef struct { int vertex[HEAP_MAX]; int dist[HEAP_MAX]; int size; } MinHeap; void heap_push(MinHeap* h, int v, int d) { if (h-size HEAP_MAX) return; // 防御性处理别让异常数据撑爆流程 int cur h-size; h-vertex[cur] v; h-dist[cur] d; while (cur 0) { int parent (cur - 1) / 2; if (h-dist[parent] h-dist[cur]) break; // 交换 parent 和 cur int tmpV h-vertex[parent]; h-vertex[parent] h-vertex[cur]; h-vertex[cur] tmpV; int tmpD h-dist[parent]; h-dist[parent] h-dist[cur]; h-dist[cur] tmpD; cur parent; } }再写 pop 最小元素int heap_pop(MinHeap* h, int* outV, int* outD) { if (h-size 0) return 0; *outV h-vertex[0]; *outD h-dist[0]; h-size--; h-vertex[0] h-vertex[h-size]; h-dist[0] h-dist[h-size]; int cur 0; while (1) { int left cur * 2 1; int right left 1; int smallest cur; if (left h-size h-dist[left] h-dist[smallest]) smallest left; if (right h-size h-dist[right] h-dist[smallest]) smallest right; if (smallest cur) break; int tmpV h-vertex[cur]; h-vertex[cur] h-vertex[smallest]; h-vertex[smallest] tmpV; int tmpD h-dist[cur]; h-dist[cur] h-dist[smallest]; h-dist[smallest] tmpD; cur smallest; } return 1; }两个函数的参数都很好理解h是堆指针v/d是插入的顶点和距离outV/outD是返回值用来接收被弹出的顶点和当时记录的距离。堆数组开多大需要提前算好同一个顶点在松弛过程中可能被 push 多次所以堆大小要比顶点数大一些才安全。4.2 堆优化版的完整代码与参数说明void dijkstra_heap(Graph* g, DijkstraResult* res, int src) { dijkstra_init(res, src); MinHeap h; h.size 0; heap_push(h, src, 0); while (h.size 0) { int u, d; heap_pop(h, u, d); // 关键跳过过期节点 if (d ! res-dist[u]) continue; res-visited[u] 1; for (int v 0; v g-n; v) { if (g-w[u][v] -1) continue; int nd d g-w[u][v]; if (nd res-dist[v]) { res-dist[v] nd; res-pre[v] u; heap_push(h, v, nd); } } } }这段代码如果用邻接矩阵时间复杂度其实还是 O(n²)因为第二层遍历邻居还是扫了全矩阵。真正要压到 O(m log n)需要把图从邻接矩阵换成邻接表#define MAXE 200005 typedef struct { int to, w, next; } Edge; Edge edges[MAXE]; int head[MAXN], ecnt; void add_edge(int u, int v, int w) { edges[ecnt].to v; edges[ecnt].w w; edges[ecnt].next head[u]; head[u] ecnt; }使用时把for (int v 0; v g-n; v)换成for (int e head[u]; e ! -1; e edges[e].next) { int v edges[e].to; int nd d edges[e].w; if (nd res-dist[v]) { res-dist[v] nd; res-pre[v] u; heap_push(h, v, nd); } }参数head[u]是顶点 u 的第一条边的下标edges[e].next指向下一条同源边。初始化时把 head 数组全部填 -1这样遍历到 -1 就结束。注意add_edge插入的是头插法输出路径时不会影响 Dijkstra 结果因为算法不依赖边的存储顺序。实现方式时间复杂度适合规模代码复杂度邻接矩阵 O(n²) 基础版O(n²)n ≈ 1000低邻接矩阵 堆O(n²)n 中等不追求极致中邻接表 堆O(m log n)n 上万、稀疏图较高手写堆翻车大多出在堆下标和元素交换上建议先用 5 个点的小图跑通再上大图。小顶堆的 size 只增不减不是pop 时 size 递减插入时递增堆内元素数量会因重复 push 变大所以要预留足够空间这也是我给出 200 万大小的原因。4.3 记录前驱 pre[]把路径一条条打出来最短路径如果只输出 dist对调试远远不够。pre 数组在松弛时记录“v 的前一个顶点是 u”最终可以沿 pre 一路回溯到起点。void print_path(DijkstraResult* res, int v) { if (v -1) return; print_path(res, res-pre[v]); printf(%d , v); }递归写法简洁但路径很长时可能爆栈。更稳的做法是用数组模拟栈int stackBuf[MAXN], top 0; for (int v target; v ! -1; v res-pre[v]) { if (top MAXN) break; stackBuf[top] v; } while (top 0) { printf(%d , stackBuf[--top]); }这里stackBuf的作用是把回溯得到的逆序路径先存起来再反向输出成从起点到终点的正确顺序。pre[v]在初始化时是 -1所以循环终止条件是v ! -1而不是v 0——如果你把顶点编号从 1 开始这里容易漏判。5. Dijkstra 的踩坑排查手册新手最容易翻车的 4 个点写 Dijkstra 的血泪经验告诉我这算法代码短但每个角落都能埋雷。下面 4 类问题是我在模拟项目和日常练习里反复看到的按“现象 → 原因 → 解决”写清楚。5.1 顶点从 1 编号却不换算最后一个顶点永远缺席现象输入明明有 5 个顶点编号 1 到 5可程序只输出 0 到 4 的距离5 号顶点要么不出现、要么输出残留值。更严重的是如果数组只开了MAXN1005大量输入会让数组越界程序在本地可能正常交付时突然崩溃。原因顶点编号没有在读边时统一减 1。算法内部遍历用的是0到n-1而输入给的是1到n两者错位。解决所有输入边和起点都统一减 1int u, v, w; scanf(%d %d %d, u, v, w); u--; v--; g.w[u][v] w;不要只在算法里把循环条件改成i n那样虽然照顾了 1 到 n却会额外处理 0 号这层空壳代码各处都要跟着改更容易出错。5.2 INF 开成 INT_MAX松弛时溢出成负数现象dist 数组出现-2147483648之类的负数甚至原本 10 的一条边被算成负数距离。原因INF定义成 2147483647dist[u] w的结果超过 int 上限C 语言 int 溢出会回绕成负数。负数比任何正数都小于是不可达顶点被错误地“松弛”整个结果立刻崩坏。解决使用0x3f3f3f3f作为 int 版 INF它约 10.6 亿两个相加也不会超过 int 上限。如果边权很大干脆用long longINF 写成0x3f3f3f3f3f3f3f3fLL。记住对比dist[u] w之前最好再加一层判断dist[u] ! INF虽然 0x3f3f3f3f 加常见边权不会溢出但这样写逻辑更干净。5.3 无向图只加单向边回程变成 INF现象从 0 到 1 输出 10把起点和终点对调后输出 1061109567也就是 INF。原因用户输入声明“无向图”代码里却只执行了g.w[u][v] w没有补反向边。邻接矩阵里w[1][0]一直是 -1反过来自然不可达。解决无向图赋值两条g.w[u][v] g.w[v][u] w;还有一种常见误解如果两个方向的通行代价不同比如上山 10、下山 5那不是无向图而是两条独立的有向边。这种情况不要自动补对称权值否则下山路会被算成上山价。5.4 堆优化忘了跳过旧节点性能惨不忍睹现象小图答案全对换成大图后运行时间暴涨甚至堆数组越界。原因同一个顶点在松弛过程中被 push 了多次堆里既有新值也有旧值。pop 出旧值时如果没有和当前 dist 比对就会拿过期数据继续松弛导致重复计算。解决pop 后立刻判断int u, d; heap_pop(h, u, d); if (d ! res-dist[u]) continue;因为算法只在nd dist[v]时更新并 push所以同一顶点在堆里的旧值一定大于当前 dist用!判断已经足够。加了这行堆里再多过期节点也只是被跳过不会影响正确性和速度。6. 把 path 数组做成调试利器一个 print_all_paths 让所有测试都变直观最后一个技巧是把路径打印做成一个通用函数每次跑完 Dijkstra 都调用它。不要把一个没打印路径的 Dijkstra 当黑匣子dist 对不一定代表 pre 对pre 指错边时单看距离完全看不出来。void print_all_paths(DijkstraResult* res, int n, Graph* g) { for (int v 0; v n; v) { if (res-dist[v] INF) { printf(to %d: unreachable\n, v); continue; } if (v ! 0 res-pre[v] -1) { printf(to %d: broken path\n, v); continue; } int seq[MAXN], top 0; for (int cur v; cur ! -1; cur res-pre[cur]) { if (top MAXN) break; seq[top] cur; } int total 0; printf(to %d: , v); for (int i top - 1; i 0; i--) { if (i top - 1) { total g-w[seq[i 1]][seq[i]]; printf( - ); } printf(%d, seq[i]); } printf( (dist%d, res-dist[v]); if (total ! res-dist[v]) printf(, WRONG path); printf()\n); } }函数里seq存的是逆序路径target 在最前面src 在最后面所以输出时从后往前。total把路径上每一条边的权值加一遍最后和res-dist[v]对比如果不相等说明 pre 数组和 dist 数组不一致要么算法有 bug要么你在 Dijkstra 之后又改过图。这一条检查能帮你抓住“答案对但路径乱”的隐蔽错误。测试时我习惯再补一个 Floyd-Warshall 对拍小图 n 不超过 7用三层 for 暴力算出所有点对最短距离然后和 Dijkstra 的输出逐点核对。Floyd 代码短作为验证器非常合适for (int k 0; k n; k) for (int i 0; i n; i) for (int j 0; j n; j) if (d[i][j] d[i][k] d[k][j]) d[i][j] d[i][k] d[k][j];我习惯把最小测试用例用注释直接写在代码顶部每次改完先跑 3 个点的图再跑刚才那组 5 点图最后才上大数据。路径打印加对拍这两步帮我躲过了不少“看似正常、换个图就翻车”的问题。遇到 Dijkstra 出错先打印路径再和 Floyd 比较比盯着代码猜快得多。希望帮到你。本文还有配套的精品资源点击获取