1. 从一张导航地图说起Dijkstra到底在算什么很多人第一次接触Dijkstra算法是在数据结构课的PPT上看到一堆节点和带权边然后老师丢出一张表格说照着填就行。但真到自己动手写C语言实现的时候问题就来了为什么需要三个数组为什么每次要选一个还没处理过的最小值为什么不能直接用BFS我换个方式来讲。你可以把Dijkstra想象成你在一个陌生城市里送外卖手里有一张地图上面标着各个路口之间的距离。你的目标是从当前站点出发找到到达每一个路口的最短路径。你不可能一次性看到全局最优解你能做的只是每次从已经确定最短距离的路口出发看看能不能通过它把周围还没确定的路口距离缩短一点。这个确定一个、松弛一圈的过程就是Dijkstra的核心节奏。它解决的是单源最短路径问题——给定一个起点求它到图中所有其他节点的最短距离。前提条件很关键边权必须非负。如果存在负权边Dijkstra的贪心策略就会失效这时候需要换Bellman-Ford或者SPFA。这个边界条件在实际工程中非常重要后面我会专门展开讲。这篇文章适合谁看如果你已经学过C语言基础语法知道数组、循环、函数怎么写但对图论算法的代码落地还不太有把握那这篇就是写给你的。我会从图的存储方式开始一步步把Dijkstra的C语言实现拆开讲清楚包括每个数组的作用、每行关键代码的意图、常见的手写错误以及如何用图解的方式验证自己的结果对不对。关键词方面围绕Dijkstra算法、C语言实现、最短路径、贪心算法、邻接矩阵、单源最短路这几个核心概念展开基本覆盖了从理论到落地的完整链路。2. 图的存储选型邻接矩阵还是邻接表在写Dijkstra之前第一件事不是写算法而是决定图怎么存。这个选择直接影响到代码的复杂度、内存占用和运行效率。很多人上来就用邻接矩阵结果遇到稀疏图边数远小于节点数平方时内存直接爆掉。所以这一步值得花时间想清楚。2.1 邻接矩阵简单直接但有代价邻接矩阵的本质是一个二维数组graph[i][j]表示从节点 i 到节点 j 的边权。如果两个节点之间没有边就设为一个足够大的数通常叫INF比如0x3f3f3f3f表示不可达。它的优点很明确判断两点之间是否有边、取边权都是O(1)的操作代码写起来非常直观。对于节点数在1000以内的稠密图邻接矩阵完全够用而且不容易出错。但代价也很明显空间复杂度是O(N²)。如果图有10000个节点那就是一亿个int大约400MB普通机器根本扛不住。而且很多位置存的是INF纯属浪费。#define MAXN 1005 #define INF 0x3f3f3f3f int graph[MAXN][MAXN]; // 邻接矩阵 int dist[MAXN]; // 起点到各点的最短距离 int visited[MAXN]; // 是否已确定最短路径这里INF取0x3f3f3f3f而不是INT_MAX是有讲究的。0x3f3f3f3f大约是10.6亿两个INF相加不会溢出int范围而INT_MAX相加会直接溢出变成负数导致松弛判断出错。这是很多人踩过的坑。2.2 邻接表稀疏图的首选邻接表用链表或数组模拟链表的方式只存实际存在的边。对于稀疏图空间复杂度降到O(NM)M是边数。在C语言里通常用结构体数组来模拟struct Edge { int to; // 目标节点 int weight; // 边权 int next; // 下一条边的索引 } edges[MAXM]; int head[MAXN]; // 每个节点的第一条边 int edge_cnt 0; void addEdge(int u, int v, int w) { edges[edge_cnt].to v; edges[edge_cnt].weight w; edges[edge_cnt].next head[u]; head[u] edge_cnt; }这种写法叫链式前向星在竞赛和工程中都很常见。它的遍历方式是从head[u]开始沿着next指针一路找下去。那到底选哪个我的经验是节点数小于1000且边比较密集用邻接矩阵节点数大或者边稀疏用邻接表。如果你只是学习算法本身邻接矩阵足够代码短、逻辑清晰、不容易出bug。如果你要处理真实路网数据比如几万个路口那必须上邻接表。提示不管用哪种存储方式建图时都要注意是无向图还是无向图。无向图需要正反各加一条边有向图只加一条。这个搞错了结果会完全不对。3. 朴素Dijkstra的完整实现与逐行拆解选好了存储方式接下来就是算法本体。朴素版本的Dijkstra时间复杂度是O(N²)适合节点数不大的场景。它的逻辑非常清晰是理解后续堆优化版本的基础。3.1 三个核心数组的分工在朴素Dijkstra中有三个数组贯穿始终每个都有明确的职责数组名作用初始化dist[]记录起点到每个节点的当前最短距离起点为0其余为INFvisited[]标记节点是否已确定最短路径全部为0graph[][]存储图的边权无边为INF有边为权值这三个数组的关系是每一轮从未访问的节点中选出dist最小的那个标记为已访问然后用它去更新邻居的dist。这个过程重复N次直到所有节点都被确定。为什么这样是对的直觉上理解如果当前所有未确定节点中dist最小的那个节点的距离还能被其他路径缩短那一定需要经过另一个未确定节点但那个节点的dist更大加上非负边权只会更大不可能更短。所以这个最小值就是最终答案。这就是贪心选择的正确性依据。3.2 核心代码逐段讲先看完整的朴素版本void dijkstra(int start, int n) { // 初始化 for (int i 1; i n; i) { dist[i] INF; visited[i] 0; } dist[start] 0; // 主循环每次确定一个节点 for (int i 1; i n; i) { // 第一步找未访问节点中dist最小的 int u -1; int minDist INF; for (int j 1; j n; j) { if (!visited[j] dist[j] minDist) { minDist dist[j]; u j; } } // 如果找不到可达节点说明剩下的都不可达 if (u -1) break; // 第二步标记为已访问 visited[u] 1; // 第三步松弛操作 for (int v 1; v n; v) { if (!visited[v] graph[u][v] ! INF) { if (dist[u] graph[u][v] dist[v]) { dist[v] dist[u] graph[u][v]; } } } } }第一段初始化没什么好说的关键是主循环里的三步。找最小值这一步遍历所有节点跳过已访问的找到dist最小的。如果所有未访问节点的dist都是INF说明剩下的节点从起点根本不可达直接break跳出不用再算了。这个细节很多人会忽略导致后面松弛时对INF做加法虽然不会出错但逻辑上不严谨。标记访问这一步把选中的节点u标记为已确定。注意标记之后就不会再被更新了因为我们已经论证过它的dist就是最终答案。松弛操作是Dijkstra的灵魂。对于u的每一个邻居v如果通过u到达v的距离比当前记录的dist[v]更短就更新它。所谓松弛就是把一条紧绷的边放松允许更短的路径通过。3.3 图解验证手动跑一遍光看代码容易晕拿一个具体例子跑一遍就清楚了。假设有5个节点边如下1→2 权值101→4 权值301→5 权值1002→3 权值503→5 权值104→3 权值204→5 权值60起点是1。初始dist [0, INF, INF, INF, INF]。第一轮选节点1标记。松弛后dist [0, 10, INF, 30, 100]。第二轮未访问中最小的是节点2dist10标记。松弛节点3dist[3] 1050 60。此时dist [0, 10, 60, 30, 100]。第三轮未访问中最小的是节点4dist30标记。松弛节点3302050 60更新为50。松弛节点5306090 100更新为90。此时dist [0, 10, 50, 30, 90]。第四轮未访问中最小的是节点3dist50标记。松弛节点5501060 90更新为60。此时dist [0, 10, 50, 30, 60]。第五轮只剩节点5标记。结束。最终从1到各点的最短距离是到2为10到3为50到4为30到5为60。你可以自己画个图验证一下1→4→3→5这条路径总长30201060确实比1→5的100和1→4→5的90都短。注意这个手动过程建议你自己在纸上画一遍。很多人看代码觉得懂了但一让自己手动推就卡壳。手动推一遍比看十遍代码都管用。4. 堆优化从O(N²)到O(M log N)的跃迁朴素版本在节点数上千之后就开始吃力了。O(N²)的瓶颈在于找最小值这一步——每轮都要线性扫描所有节点。如果用小顶堆优先队列来维护未访问节点的dist每次取最小值就变成O(log N)整体复杂度降到O(M log N)。对于稀疏图这是质的飞跃。4.1 为什么C语言里要手写堆C有priority_queue可以直接用但C语言标准库没有现成的优先队列。你可以选择手写一个二叉堆或者用更取巧的办法。手写堆不难核心就是两个操作上浮push时维护堆性质和下沉pop时维护堆性质。typedef struct { int node; int dist; } HeapNode; HeapNode heap[MAXM]; int heapSize 0; void heapPush(int node, int dist) { heap[heapSize].node node; heap[heapSize].dist dist; int i heapSize; while (i 1) { int parent i / 2; if (heap[parent].dist heap[i].dist) break; HeapNode tmp heap[parent]; heap[parent] heap[i]; heap[i] tmp; i parent; } } HeapNode heapPop() { HeapNode top heap[1]; heap[1] heap[heapSize--]; int i 1; while (i * 2 heapSize) { int child i * 2; if (child 1 heapSize heap[child 1].dist heap[child].dist) child; if (heap[i].dist heap[child].dist) break; HeapNode tmp heap[i]; heap[i] heap[child]; heap[child] tmp; i child; } return top; }这段代码是标准的二叉堆实现。heapPush把新元素放到末尾然后上浮heapPop把堆顶和末尾交换后下沉。注意数组从下标1开始用这样父子节点关系是i/2和i*2、i*21比从0开始更简洁。4.2 堆优化版本的完整流程有了堆之后Dijkstra的主循环变成void dijkstraHeap(int start, int n) { for (int i 1; i n; i) dist[i] INF; dist[start] 0; heapPush(start, 0); while (heapSize 0) { HeapNode cur heapPop(); int u cur.node; int d cur.dist; // 关键跳过过期条目 if (d dist[u]) continue; // 遍历u的所有邻居邻接表 for (int e head[u]; e ! 0; e edges[e].next) { int v edges[e].to; int w edges[e].weight; if (dist[u] w dist[v]) { dist[v] dist[u] w; heapPush(v, dist[v]); } } } }这里有一个非常关键的细节if (d dist[u]) continue;。为什么需要这一行因为同一个节点可能被多次压入堆中。比如节点v先以距离100入堆后来找到更短路径距离50又入堆一次。堆里就有两个v的条目。当弹出距离100的那个时dist[v]已经是50了d100 dist[v]50直接跳过。这个判断叫懒惰删除是堆优化Dijkstra的标准写法。如果不加这一行虽然结果可能也对因为后面还会用50的条目再处理一次但会做大量无用功严重时复杂度退化。所以这一行不是可选项是必须的。4.3 两种实现的性能对比对比项朴素Dijkstra堆优化Dijkstra时间复杂度O(N²)O(M log N)空间复杂度O(N²)邻接矩阵O(NM)邻接表适用场景稠密图、小规模稀疏图、大规模代码复杂度低中1000节点10000边实测约5ms约1ms10000节点100000边实测内存溢出约50ms这个表格里的实测数据是基于常见配置的粗略估计具体数值会因机器和编译器优化不同而有差异但量级关系是可靠的。可以看到规模一大朴素版本直接因为邻接矩阵的内存问题出局。提示如果你的图是稠密图M接近N²堆优化反而不一定有优势因为每次松弛都可能入堆堆操作次数是M级别的。这时候朴素O(N²)可能更快。选型要看具体数据特征不要盲目上堆。5. 那些年我踩过的坑从WA到AC的排查链路代码写完了跑出来结果不对这才是最折磨人的阶段。我把自己和身边人踩过的坑整理成一条排查链路你遇到问题时可以按顺序检查。5.1 距离初始化与INF的选择最常见的错误是INF设成了INT_MAX然后在松弛时做dist[u] w直接整数溢出变成负数导致所有判断都出错。这个bug非常隐蔽因为小数据量下可能碰巧不出问题一上大数据就崩。正确的做法是用0x3f3f3f3f它的两倍还在int范围内。或者用long long存距离INF设为0x3f3f3f3f3f3f3f3f。我个人的习惯是后者更保险。另一个相关问题是初始化不完整。每次调用Dijkstra前dist和visited都要重新初始化。如果只初始化一次多组测试数据就会互相污染。这个错误在多组输入的题目里特别常见。5.2 有向图与无向图的混淆建图时忘了无向图要加两条边或者有向图加了两条边结果距离偏大或偏小。这个错误的特点是小例子可能看不出来因为有些边恰好不影响最终结果。建议建完图后打印一下邻接矩阵或邻接表肉眼核对一遍。5.3 节点编号从0还是从1开始这个问题看似小但引发的bug不少。如果节点编号从0开始循环就要写成for (int i 0; i n; i)堆的父子关系也要相应调整。混用0起始和1起始轻则数组越界重则结果全错。我的建议是统一从1开始多开一个空间省去大量下标换算的心智负担。5.4 堆优化中忘记跳过过期条目前面提过的if (d dist[u]) continue;漏写这行不会导致结果错误但会让程序变慢。更隐蔽的情况是有人用visited数组来跳过但visited标记的是已确定而过期条目对应的节点可能还没被确定逻辑上不对。正确做法就是用d dist[u]判断。5.5 排查链路总结遇到结果不对时按这个顺序查打印初始dist数组确认起点为0其余为INF打印邻接矩阵/邻接表确认边权和方向正确手动跑一个小例子4-5个节点对比程序输出检查INF的值和加法是否溢出检查节点编号起始是否一致堆优化版本检查是否跳过过期条目这条链路能覆盖90%以上的常见错误。剩下10%通常是题目本身的特殊要求比如要求输出路径而不只是距离那就需要额外维护一个pre[]数组记录前驱节点。6. 路径还原与多场景扩展算出最短距离只是第一步很多实际场景还需要知道具体走哪条路。比如导航不仅要告诉你多远还要告诉你怎么走。这就需要在松弛时记录前驱节点。6.1 用pre数组还原完整路径在松弛操作里加一行if (dist[u] w dist[v]) { dist[v] dist[u] w; pre[v] u; // 记录v的前驱是u heapPush(v, dist[v]); }最后从终点不断找pre就能回溯出路径void printPath(int start, int end) { if (end start) { printf(%d, start); return; } printPath(start, pre[end]); printf( - %d, end); }注意pre数组也要初始化起点的pre设为-1或自身。如果终点不可达pre可能没被更新过需要额外判断。6.2 多源最短路与Floyd的取舍有时候起点不止一个比如多个仓库到多个配送点。这时候有两个选择一是加一个虚拟源点到所有真实源点连权值为0的边跑一次Dijkstra二是直接用Floyd算法求所有点对的最短路。Floyd是O(N³)代码极短三重循环五行搞定。如果节点数在500以内Floyd的简洁性优势明显。但如果节点数上千Floyd就太慢了还是老老实实对每个源点跑Dijkstra。场景推荐算法理由单源、稀疏图堆优化Dijkstra快内存省单源、稠密图朴素Dijkstra代码简单常数小多源、节点少Floyd五行代码不易错多源、节点多虚拟源点Dijkstra效率高有负权边Bellman-Ford/SPFADijkstra不适用6.3 实际工程中的注意事项在真实项目里用Dijkstra有几个课本上不会讲但很重要的点。第一数据规模决定一切。先估算节点数和边数再选存储结构和算法版本。不要一上来就写堆优化也不要死守邻接矩阵。第二距离类型要用long long。如果边权可能很大比如实际距离以米为单位累加后超过int范围用int会溢出。这个错误在测试数据小的时候发现不了上线后才爆。第三注意重边和自环。两个节点之间可能有多条边取权值最小的那条。自环节点到自己的边直接忽略因为非负权下自环不会让路径更短。邻接矩阵天然处理重边取min即可邻接表需要在建图时判断或让算法自然处理。第四性能敏感场景考虑配对堆或斐波那契堆。二叉堆的decrease-key操作是O(log N)而配对堆可以把某些操作降到O(1)均摊。不过实现复杂度高很多除非确实遇到性能瓶颈否则二叉堆够用。我在一个模拟路网项目里用过堆优化Dijkstra节点约5万边约12万单次查询在普通机器上大约30-50毫秒。这个性能对于交互式查询完全可以接受。如果要做实时导航那种毫秒级响应就需要上A*或者Contraction Hierarchies这类进阶算法了但那是在Dijkstra基础上做的优化底层逻辑还是相通的。把Dijkstra吃透不只是学会一个算法更是理解贪心松弛这套思路的入口。后面很多最短路变种、最小生成树、甚至网络流的一些算法都能看到类似的影子。代码写一遍、手动推一遍、踩几个坑再调一遍这个算法就真正长在你身上了。
