简介面向数据结构与C/C算法学习者的Dijkstra最短路径实现资料聚焦单源点最短路径问题覆盖图的创建、图的存储以及最短路径计算等核心环节。内容适合课程设计、算法入门和路径规划类练习也能对应交通旅游、城市规划、电网架设等实际场景帮助读者把结构体、指针与图结构知识落到可编译的C语言程序上。压缩包共2个文件包含1个cpp源码和1个doc文档整体约139KB源码便于编译调试与二次修改文档可用于梳理算法思路和实现说明。已有11696人学习下载具备较好的参考基础。读者可据此理解Dijkstra算法的选点、距离更新与路径回溯过程掌握图存储的具体写法并借助文档排查常见实现问题适合需要完成单源最短路径作业、课程设计或快速搭建算法原型的读者参考。1. 从园区导航绕路说起这份最短路径 Dijkstra 算法 C 语言实现到底能干什么前阵子帮人做一个园区内部的小工具需求很朴素输入两个门禁点的编号输出一条最短步行路线顺带告诉用户总长度。图不大几百个点、上千条边试了几个现成的库都嫌重编译链一拉就是一堆依赖最后干脆自己用 C 撸了一个 Dijkstra 内核几十 KB 的源码gcc一敲就能出可执行文件。这份「最短路径 Dijkstra 算法 C 语言实现」源码包走的就是这个路子它不是教学 PPT 里的伪代码而是一份能编译、能读文件、能打印完整路径、也方便你换存储结构的工程化实现。适合谁看正在做课设、嵌入式寻路、游戏格子地图、网络拓扑计算或者单纯想把图算法从「背模板」变成「能改」的开发者。它不解决超大图千万级节点请左转去用专门的图计算框架但在 10 万点以内、边权非负的场景里够用且可控。2. 工程结构与编译链几个文件撑起一个能跑的内核拿到一份 C 项目我第一件事不是看算法而是先看目录和 Makefile这两样决定了它能不能在三分钟内跑起来。这个包的结构很克制头文件、实现、入口、数据、测试脚本各归各位没有把两千行代码塞进一个main.c里——这一点比很多同类代码强至少它默认你会去改。2.1 目录骨架与每个文件的责任边界典型的目录长这样dijkstra-c/ ├── Makefile ├── README.md ├── include/ │ ├── graph.h /* 图结构、建边接口 */ │ ├── heap.h /* 二叉堆只管排序不管图 */ │ └── dijkstra.h /* 对外只暴露一个求解函数 */ ├── src/ │ ├── graph.c /* 链式前向星的增删与释放 */ │ ├── heap.c /* 上浮/下沉与图完全解耦 */ │ ├── dijkstra.c /* 松弛 路径回溯 */ │ └── main.c /* 读文件、调接口、打印 */ ├── data/ │ ├── sample.txt /* 十来个点的小样例肉眼可验算 */ │ └── grid_1k.txt /* 1000 点网格用来压时间 */ └── tests/ └── run_tests.sh /* 批量跑样例并 diff 期望输出 */graph负责「图长什么样」heap负责「谁最小先出」dijkstra只做松弛这一件事。这种切法最直接的好处是你想换成邻接矩阵只动graph.cdijkstra.c一行不用改你想换成配对堆或者直接上O(n^2)的朴素版只动heap那层。二次开发最怕的就是「算法逻辑和数据结构焊死」这个包避开了这个坑。2.2 编译方式与 Makefile 里的关键开关gcc单文件手敲当然行但项目给了 Makefile就该用起来CC ? gcc CFLAGS ? -O2 -stdc11 -Wall -Wextra -pedantic -Iinclude TARGET : bin/dijkstra SRCS : $(wildcard src/*.c) OBJS : $(SRCS:src/%.cbuild/%.o) all: $(TARGET) $(TARGET): $(OBJS) mkdir -p $(dir $) $(CC) $(OBJS) -o $ build/%.o: src/%.c mkdir -p build $(CC) $(CFLAGS) -c $ -o $ run: $(TARGET) ./$(TARGET) data/sample.txt clean: rm -rf build bin .PHONY: all run clean三个地方值得留意。-stdc11是因为代码里用了复合字面量(HeapNode){nd, to}和指定初始化器C89 编译会直接报错-Wall -Wextra -pedantic建议别删C 代码里最容易翻车的就是有符号/无符号比较和隐式截断让编译器先替你骂一遍-Iinclude保证src/*.c里写#include graph.h就能找到头文件不用写一堆相对路径。-O2在堆优化版本上大概能带来 1.5 到 2 倍的速度差跑大样例的时候很明显。日常三条命令make出可执行文件make run跑内置样例make clean清干净。如果换到 Windows 上MinGW 的mingw32-make直接吃这份 Makefile不需要改MSVC 用户则需要自己建工程把src/*.c全加进去并把include加到头文件搜索路径。2.3 输入格式与输出约定先对齐再谈算法这个包用的是一种很省事的文本格式第一行四个整数后面是边n m s t u v w ... u v wn是顶点数编号 0 到 n-1m是边数s是源点t是终点。接下来m行每行一条边起点、终点、非负权值。对应data/sample.txt类似6 8 0 5 0 1 7 0 2 9 0 5 14 1 2 10 1 3 15 2 3 11 2 5 2 3 4 6读入这一段就是十几行 C/* main.c 片段读图入口 */ int main(int argc, char **argv) { const char *path (argc 1) ? argv[1] : data/sample.txt; FILE *fp fopen(path, r); if (!fp) { perror(fopen); return 1; } int n, m, s, t; if (fscanf(fp, %d %d %d %d, n, m, s, t) ! 4) { fprintf(stderr, bad header\n); fclose(fp); return 1; } Graph g; if (graph_init(g, n, m) ! 0) { fclose(fp); return 1; } for (int i 0; i m; i) { int u, v, w; if (fscanf(fp, %d %d %d, u, v, w) ! 3) { /* 中途坏行直接报错 */ fprintf(stderr, bad edge at line %d\n, i 2); graph_free(g); fclose(fp); return 1; } if (u 0 || u n || v 0 || v n) { /* 越界保护别等跑飞了再查 */ fprintf(stderr, vertex out of range: %d %d\n, u, v); graph_free(g); fclose(fp); return 1; } graph_add_edge(g, u, v, w, 1); /* 默认有向图 */ } fclose(fp); int *dist (int *)malloc(sizeof(int) * n); int *prev (int *)malloc(sizeof(int) * n); if (!dist || !prev) { graph_free(g); free(dist); free(prev); return 1; } if (dijkstra(g, s, dist, prev) 0) { if (dist[t] INF) printf(dist[%d] unreachable\n, t); else printf(dist[%d] %d\n, t, dist[t]); print_path(prev, n, s, t); } free(dist); free(prev); graph_free(g); return 0; }graph_add_edge的最后一个参数是方向开关1为有向、0为无向。这是很容易忽略的一个细节用同一个函数处理两种图比另写一个add_undirected要省事但一定要在main里明确写死别让默认值藏在函数签名里——我见过太多次「明明是双向路网结果只建了单向边」的事故。输出约定是两行dist[t] 数字或unreachable然后一行path: 0 - 2 - 5这样的完整路径。把路径单独打出来是个好设计只有距离没有路径的实现调试的时候就是个黑匣子你根本不知道它是算对了还是凑巧撞对了。3. 存储结构选型邻接矩阵、邻接表还是链式前向星C 语言写图算法第一个分叉口就在这儿。选错了不是跑不动是跑到一半才发现不该这么选——那时候改起来牵连一大片。3.1 三种存法在 C 里的取舍邻接矩阵最好写int g[N][N]一把梭但 10 万点就是 400 亿字节别想了邻接表用int **adj加变长数组灵活但每个顶点一次malloc指针跳来跳去缓存不友好链式前向星用一个大数组装所有边head[u]指向第一条出边每条边存一个next串成链表既没有碎片也没有多次分配。这个包选的是第三种。存储方式空间遍历出边实现难度适合规模邻接矩阵O(n²)O(n)最低n 2000邻接表O(nm)O(deg)中通用链式前向星O(nm)O(deg)中大图、竞赛、嵌入式选前向星还有一个隐性好处所有边在内存里连续排列遍历同一个点的出边时访存顺序基本是线性的比链式malloc出来的节点快不少。在 100 万边的规模上这个差距能到肉眼可见的地步。3.2 边表结构体与前向星的插入/* graph.h */ #ifndef GRAPH_H #define GRAPH_H #define INF 0x3f3f3f3f /* 约 10.6 亿两个 INF 相加也不会溢出 int */ typedef struct Edge { int to; /* 这条边指向的顶点编号 */ int w; /* 边权必须非负 */ int next; /* 同一起点的下一条边下标-1 表示没有 */ } Edge; typedef struct Graph { int n; /* 顶点数 */ int m; /* 已加入的边数含正反两条 */ int cap; /* edges 的容量按 2 * 预估边数 开 */ int *head; /* 长度 n值为第一条出边的下标-1 表示无出边 */ Edge *edges; /* 长度 cap所有边挤在一块连续内存里 */ } Graph; int graph_init(Graph *g, int n, int m); void graph_add_edge(Graph *g, int u, int v, int w, int directed); void graph_free(Graph *g); #endifINF用0x3f3f3f3f而不是INT_MAX血泪经验dist[u] w在INT_MAX上再加一个非零数会溢出成负数结果 Dijkstra 认为找到了更短的路答案直接歪到天边。0x3f3f3f3f大约 10.6 亿两个相加 21 亿还在int范围内。插入逻辑/* graph.c */ #include graph.h #include stdlib.h int graph_init(Graph *g, int n, int m) { g-n n; g-m 0; g-cap 2 * m 2; /* 无向图正反各一条留点余量 */ g-head (int *)malloc(sizeof(int) * n); g-edges (Edge *)malloc(sizeof(Edge) * g-cap); if (!g-head || !g-edges) { free(g-head); free(g-edges); g-head NULL; g-edges NULL; return -1; } for (int i 0; i n; i) g-head[i] -1; /* 初始化成没有出边 */ return 0; } void graph_add_edge(Graph *g, int u, int v, int w, int directed) { if (g-m g-cap) return; /* 容量是预估的超了就丢别越界 */ g-edges[g-m] (Edge){ v, w, g-head[u] }; /* 头插新边指向原来的第一条 */ g-head[u] g-m; if (!directed) { g-edges[g-m] (Edge){ u, w, g-head[v] }; g-head[v] g-m; } }参数u、v、w分别是起点、终点、权值directed为 0 时再补一条反向边。头插法让新边总是排在链表第一个写起来最省事代价是遍历顺序和输入顺序相反——对 Dijkstra 的正确性没有影响但如果你要复现某份参考答案的路径这一点得心里有数。cap直接按2*m2估死是刻意的取舍。动态扩容每次要realloc并搬移全部边还会让head里存的旧下标失效复杂度反而上去了。工程上更常见的做法是先扫一遍文件数清楚有多少条边再graph_init——这一步在main里加十行就够但对大文件来说能省掉一半内存重新分配。3.3 dist / prev / 堆三件套的内存布局Dijkstra 除图本身之外还要三块内存这三块怎么放直接决定了函数签名和调用方的使用方式。dist[v]存源点到v的当前最短距离初始全是INF源点为 0prev[v]存最短路径上v的前驱顶点初始全-1用来最后倒推路径堆里存的是(当前距离, 顶点号)二元组按距离小根堆。这三样都由调用方传进来dijkstra函数内部不malloc也不持有它们的生命周期:/* dijkstra.h */ #ifndef DIJKSTRA_H #define DIJKSTRA_H #include graph.h /* dist/prev 由调用方分配长度均 g-n返回 0 表示正常完成 */ int dijkstra(const Graph *g, int src, int *dist, int *prev); /* 从 prev 数组倒推并打印 src-dst 的完整路径 */ void print_path(const int *prev, int n, int src, int dst); #endif这种「谁分配谁释放」的约定在 C 项目里应该成为默认做法。我见过把dist声明成函数内static数组的实现单次调用没问题一旦要并发跑多个源点就立刻串数据而且大小写死之后换数据集就得改源码重编。传指针进来虽然多写两行malloc但换来了复用和可测性。4. 核心链路拆解一次 run 从读图到路径输出的完整过程到这一层图已经建好、内存已经备齐剩下的就是 Dijkstra 本身。堆优化版的骨架其实很短真正容易写错的都在细节里。4.1 初始化、松弛与懒删除/* dijkstra.c */ #include dijkstra.h #include heap.h #include stdlib.h int dijkstra(const Graph *g, int src, int *dist, int *prev) { const int n g-n; for (int i 0; i n; i) { /* 步骤一全部置为不可达 */ dist[i] INF; prev[i] -1; } Heap h; if (heap_init(h, n) ! 0) return -1; /* 堆容量按点数估够用 */ dist[src] 0; heap_push(h, (HeapNode){ 0, src }); /* 步骤二源点入堆 */ while (!heap_empty(h)) { HeapNode cur heap_pop(h); /* 懒删除堆里可能残留同一个点的旧距离比当前 dist 大的直接丢 */ if (cur.d dist[cur.v]) continue; /* 步骤三遍历 cur.v 的每一条出边做松弛 */ for (int e g-head[cur.v]; e ! -1; e g-edges[e].next) { int to g-edges[e].to; int nd cur.d g-edges[e].w; if (nd dist[to]) { dist[to] nd; prev[to] cur.v; if (heap_push(h, (HeapNode){ nd, to }) ! 0) { heap_free(h); return -1; } } } } heap_free(h); return 0; }逐段看。第一段初始化没什么可说的prev置-1是给后面的路径回溯留标记。第二段把源点距离设为 0 并入堆注意这里不需要单独维护一个visited数组——懒删除加dist比较就把「出堆即确定」这件事兜住了少一个数组也少一次判断。第三段是核心。cur.d dist[cur.v]这个判断不能写成!也不能省略。堆里同一个顶点可能有多条记录比如先入堆一个dist9、后来发现dist5又入堆一次那么老的9出堆时9 5成立跳过而如果误用!同样成立看起来一样但万一堆里出现两条完全相同的记录!就不成立了会重复松弛虽然答案不会错但白跑一遍。用是最稳的写法。nd dist[to]用的是严格小于重复边两点之间多条不同权值的边在这是安全的只要有一条更短的就会被更新一次多余的记录会在出堆时被懒删除掉。prev[to] cur.v必须在更新dist的同一分支里改否则回溯出来的是一条「距离对但路径不对」的假路径——这种 bug 最难查因为距离输出是全对的。4.2 手写二叉堆五十行的代价换一个数量级/* heap.h */ #ifndef HEAP_H #define HEAP_H typedef struct { int d; /* 入堆时的距离快照之后不会再改 */ int v; /* 顶点编号 */ } HeapNode; typedef struct { HeapNode *a; int size; int cap; } Heap; int heap_init(Heap *h, int cap); void heap_free(Heap *h); int heap_push(Heap *h, HeapNode x); /* 0 成功-1 失败 */ HeapNode heap_pop(Heap *h); /* 调用前须保证非空 */ static inline int heap_empty(const Heap *h) { return h-size 0; } #endif/* heap.c */ #include heap.h #include stdlib.h static void swap_node(HeapNode *a, HeapNode *b) { HeapNode t *a; *a *b; *b t; } int heap_init(Heap *h, int cap) { h-cap (cap 4) ? cap : 4; h-a (HeapNode *)malloc(sizeof(HeapNode) * h-cap); h-size 0; return h-a ? 0 : -1; } void heap_free(Heap *h) { free(h-a); h-a NULL; h-size h-cap 0; } int heap_push(Heap *h, HeapNode x) { if (h-size h-cap) { /* 扩容翻倍摊还 O(1) */ int nc h-cap * 2; HeapNode *p (HeapNode *)realloc(h-a, sizeof(HeapNode) * nc); if (!p) return -1; h-a p; h-cap nc; } int i h-size; h-a[i] x; while (i 0) { /* 上浮比父节点小就往上换 */ int parent (i - 1) 1; if (h-a[parent].d h-a[i].d) break; swap_node(h-a[parent], h-a[i]); i parent; } return 0; } HeapNode heap_pop(Heap *h) { HeapNode top h-a[0]; h-a[0] h-a[--h-size]; /* 尾元素搬到根 */ int i 0; for (;;) { /* 下沉挑较小的孩子换上来 */ int l 2 * i 1, r l 1, small i; if (l h-size h-a[l].d h-a[small].d) small l; if (r h-size h-a[r].d h-a[small].d) small r; if (small i) break; swap_node(h-a[i], h-a[small]); i small; } return top; }这个堆只按d排序v只是载荷、不参与比较。有人会想「距离相等时按顶点编号排一下更稳定」能用但完全没必要——Dijkstra 的正确性和出堆顺序无关只和「取出的一定是当前最小值」有关。heap_push里用而不是判断停止上浮是为了让相等的元素不去换位少写几次内存。这个细节在百万级操作里能省下几个百分点的耗时属于那种「不写也对、写了更好」的东西。对比一下朴素版不用堆的话每轮需要O(n)扫描找最小值总共O(n²)换成堆以后是O((n m) log n)。1000 点 10000 边的图上堆优化大概是朴素版速度的三到五倍到了 10 万点差距就是一个能跑完、一个跑不完的区别。这也是为什么这个包即使代码长了五十行也仍然默认用堆。4.3 路径回溯与不可达处理/* dijkstra.c 续路径打印 */ #include stdio.h void print_path(const int *prev, int n, int src, int dst) { if (src dst) { printf(path: %d\n, src); return; } if (dst 0 || dst n || prev[dst] -1) { printf(path: unreachable\n); /* 源点自身 prev 也是 -1前面已排除 */ return; } int *buf (int *)malloc(sizeof(int) * n); if (!buf) return; int top 0, cur dst; while (cur ! -1 top n) { /* 从终点一路沿 prev 往回走 */ buf[top] cur; cur prev[cur]; } if (cur ! -1) { /* 走不到头说明 prev 成环了属于数据问题 */ free(buf); printf(path: broken (cycle detected)\n); return; } printf(path: ); for (int i top - 1; i 0; --i) /* 倒着存的路径反向打印 */ printf(%d%s, buf[i], i ? - : \n); free(buf); }回溯依赖prev数组本质是一棵以源点为根的最短路径树从任意终点沿父指针走到根就是一条路径。这里用malloc而不用 VLA 或者固定大小栈数组是因为n可能上万栈上开数组很容易直接段错误top n这个上限则是防御prev被意外写坏成环——正常数据不会触发但真遇上脏数据的时候一行path: broken比进程卡死强得多。参数n是顶点数同时也是路径长度的理论上限最短路不会重复经过顶点。打印顺序是从buf尾部倒着输出因为循环是终点往源点走的。用i ? - : \n控制分隔符比在循环里加if判断少一层缩进读起来干净。5. 排查与避坑跑不通、答案偏、规模一大就崩的现场记录这些坑基本都被我在不同项目里踩过一遍写出来省你几个小时。5.1 现象距离输出突然变成负数或极大值原因几乎总是INF选得太大。用INT_MAX约 21.4 亿做无穷大松弛时dist[u] w直接溢出回绕成负数随后被当成「更短的路」写进dist整张图的答案连锁崩掉。解决统一用0x3f3f3f3f并在代码里加一句断言INF 2 * max_w。如果边权可能到 10 亿量级就把dist换成long longINF用0x3f3f3f3f3f3f3f3fLL别硬撑int。5.2 现象明明是无向路网算出来的路要走回头路一样距离偏大graph_add_edge的directed参数传了 1或者干脆忘了反向建边。无向图只建单向边Dijkstra 会认为从v到u不通路径要么绕远要么判不可达。解决读文件时把方向开关抽成配置项sample.txt第一行后面跟一个D/U标记或者单独写两个数据文件。跑之前先打印一遍g.m无向图的边数应该正好是输入行数的两倍对不上就是这里出问题。5.3 现象小图秒出一到几万点就卡住几十秒八成是懒删除的判断写成了if (cur.d ! dist[cur.v]) continue;或者干脆没写这一句。没写的话堆里塞了大量过期记录每个都出堆并重复遍历出边复杂度退化成接近O(m²)级别的实际表现。解决确认判断条件是另外检查heap_init的容量如果按顶点数给但图很稠密每个点出度几十堆会频繁realloc一次扩容就是整块搬移。这时候按2*m给初始容量或者干脆做一个「预分配 一次性扩容」的版本。5.4 现象换了数据源以后带权图跑出来和最短路明显不符输入里出现了负权边。Dijkstra 的前提是边权非负有负边的时候它会把已经确定的点重新变短而算法已经不再回头看它了答案必错。这不是实现 bug是算法适用边界。解决读入时顺手检查if (w 0)直接报错退出别让它静默跑完给一个错的答案。真有负权需求换成 Bellman-Ford 或者 SPFA但那是另一个话题了别在 Dijkstra 上打补丁。5.5 现象小样例全对跑 10 万点的文件立刻段错误典型是在栈上开了大数组比如int dist[100000]或者Edge edges[2000000]。Linux 默认栈 8MB一个Edge结构体 12 字节两百万条就是 24MB直接爆栈。解决一律malloc并在graph_init里检查返回值。顺带一提valgrind --toolmemcheck ./bin/dijkstra data/grid_1k.txt跑一遍能抓到漏掉的graph_free和越界写这类内存问题用肉眼查太慢。6. 二次开发把这个内核改成你自己的寻路模块真正动手改的时候最容易卡住的不是算法而是「怎么把业务概念映射成顶点和边」。以网格地图为例每个格子就是一个顶点四邻域相邻就是一条权值为 1 的边static inline int id_of(int r, int c, int cols) { return r * cols c; } /* grid 里 # 表示障碍. 表示可走先数一遍边再 init避免容量估错 */ int edges 0; for (int r 0; r rows; r) for (int c 0; c cols; c) { if (grid[r][c] #) continue; if (r 1 rows grid[r 1][c] ! #) edges; if (c 1 cols grid[r][c 1] ! #) edges; } Graph g; graph_init(g, rows * cols, edges); for (int r 0; r rows; r) for (int c 0; c cols; c) { if (grid[r][c] #) continue; if (r 1 rows grid[r 1][c] ! #) graph_add_edge(g, id_of(r, c, cols), id_of(r 1, c, cols), 1, 0); if (c 1 cols grid[r][c 1] ! #) graph_add_edge(g, id_of(r, c, cols), id_of(r, c 1, cols), 1, 0); }二维坐标压成一维id是为了让dist、prev继续用一维数组回溯出来的整数序列再反解成坐标即可。换成八邻域只是多四条if换成带地形成本的网格草地 1、泥地 3、道路 0.5把权值改成查表cost[r][c]就行——但注意权值必须是整数0.5这类要么整体乘 10要么把Edge.w和dist全换成浮点别混着用。改完之后一定要验证不能只看「跑出来了」。我的做法是准备三类用例手工可推的小图六七条边答案写在注释里、n1和不可达的边界图、以及一个随机生成的对拍脚本——用O(n²)的朴素 Dijkstra 写一份二十行的参考实现两个版本在几百个随机图上比对dist数组全部一致才算过。这一步看起来笨但它能挡住上面第五章里至少三个坑。再往下走如果图是静态的、查询次数很多可以在外面加一层缓存或一次性预计算如果边权会变就得考虑增量更新而不是每次全量重跑。至于源码包本身从data/sample.txt跑通、把main.c里的输出格式换成你自己的接口约定、再把graph_init的容量估算换成实际统计值这四步做完就基本能接进真实工程了。这类活儿干多了以后我形成了个习惯任何图算法代码先不看算法部分先用小样例把dist数组整个打出来对一遍再谈性能。因为路径和距离一旦对上剩下的就只是工程问题反过来如果一开始就闷头优化堆最后发现是建图时方向搞反了那才是真的浪费一天。希望帮到你。本文还有配套的精品资源点击获取