★ FEATURED ARTICLE 1. 从一道题看透Dijkstra的本质1.1 这道题到底在问什么“最小花费”这个标题看起来平平无奇但它几乎是每个学图论的人都会撞上的一道经典题。题目的核心场景通常是这样给定n个点、m条边每条边有一个“花费”权重要求从起点到终点走哪条路总花费最小。有时候是求单点到单点有时候是求单点到所有点还有时候会加一点变形比如“花费”不是简单相加而是相乘、或者有汇率转换的味道。我第一次碰到这类题的时候脑子里第一反应是DFS暴力枚举所有路径。结果数据范围一上来n1000、m10000直接超时到怀疑人生。后来才明白这类“边权非负、求最短路径”的问题就是Dijkstra算法的主场。这道题适合谁如果你刚学完图的存储邻接矩阵或邻接表想找一个能真正跑起来的练手题那它非常合适。如果你已经写过几遍Dijkstra但总是TLE或者WA那这篇文章里关于堆优化和边界处理的细节应该能帮你把坑填上。1.2 为什么是Dijkstra而不是别的图的最短路算法有好几个选哪个不是拍脑袋决定的。我把常见选择的逻辑整理一下算法适用条件时间复杂度典型场景Dijkstra边权非负O((nm)logn) 堆优化单源最短路边权为正Bellman-Ford允许负权O(nm)含负权边、判负环Floyd多源最短路O(n³)n很小求任意两点距离BFS边权全为1O(nm)无权图或等权图“最小花费”这类题花费通常是正数钱不可能是负的所以Dijkstra是最优解。Bellman-Ford虽然也能做但复杂度高一个量级没必要。Floyd在n≤500的时候可以考虑但n一大就废了。注意如果题目里出现了“花费可以为负”或者“有返现”这种描述那Dijkstra就不能用了必须换Bellman-Ford。这是很多人踩过的坑——看到最短路就无脑上Dijkstra结果负权边直接让贪心策略失效。1.3 贪心思想的生活化理解Dijkstra的核心是贪心每次从“还没确定的点”里挑一个当前距离最小的把它标记为“已确定”然后用它去更新邻居的距离。你可以这样理解假设你要从家去某个陌生城市手里有一张地图上面标了各段路的油费。你先把所有城市分成两类——“已经确定最便宜路线的”和“还没确定的”。一开始只有家是确定的距离为0。然后你每次从没确定的城市里挑一个当前累计油费最少的认为“到它的最便宜路线已经找到了”再用它去修正其他城市的油费估计。为什么这个贪心是对的因为所有边的权重都是非负的。如果你当前到A的估计是10到B的估计是20那么从B绕道去A不可能更便宜——因为从B到A至少还要加一个非负的权重只会让总花费更大。这个性质保证了“当前最小的估计值就是最终答案”。2. 核心细节与实现要点拆解2.1 图的存储方式怎么选存储方式直接决定了代码的效率和写法。常见的有三种邻接矩阵g[i][j]表示i到j的边权。优点是写起来简单更新和查询都是O(1)。缺点是空间O(n²)n10000的时候就是1亿个int直接爆内存。只适合n≤1000的小数据。邻接表vector版vectorpairint,int g[n]每个点存一个邻居列表。空间O(nm)适合稀疏图。写起来也不复杂是我最常用的方式。链式前向星用数组模拟链表head[]、nxt[]、to[]、w[]四个数组。空间最省速度最快但写起来稍微绕一点。竞赛里常用日常练习用vector就够了。“最小花费”这类题m通常远小于n²所以邻接表是首选。我一般直接写vectorpairint,int g[MAXN]; // g[u] {v, w}2.2 朴素版Dijkstra的完整逻辑朴素版的时间复杂度是O(n²)适合n≤1000的情况。核心步骤初始化dist[]数组为无穷大dist[start]0。用一个visited[]数组标记已确定的点。循环n次每次找一个未访问且dist最小的点u标记visited[u]true然后遍历u的所有邻居v如果dist[u]w dist[v]就更新dist[v]。这里有个细节很多人会写错找最小dist的点时如果找不到dist为无穷大说明剩下的点都不可达可以直接break。不加这个判断虽然不会错但会多跑一些无用的循环。void dijkstra(int start, int n) { for (int i 1; i n; i) dist[i] INF; dist[start] 0; memset(visited, 0, sizeof(visited)); for (int i 1; i n; i) { int u -1, minD INF; for (int j 1; j n; j) { if (!visited[j] dist[j] minD) { minD dist[j]; u j; } } if (u -1) break; visited[u] true; for (auto [v, w] : g[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; } } } }2.3 堆优化版的关键改动朴素版每次找最小点要O(n)总共O(n²)。用优先队列小根堆可以把这一步降到O(logn)整体复杂度变成O((nm)logn)。改动只有两处一是用priority_queue维护(dist, node)对每次直接取堆顶二是需要处理“过期”的堆元素——因为同一个点可能被多次入堆如果取出来的dist比当前记录的dist大说明是旧数据直接跳过。void dijkstra(int start, int n) { for (int i 1; i n; i) dist[i] INF; dist[start] 0; priority_queuepairint,int, vectorpairint,int, greater pq; pq.push({0, start}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; // 过期元素跳过 for (auto [v, w] : g[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } }提示greater让优先队列变成小根堆。默认的priority_queue是大根堆取出来的是最大值那就完全反了。这个点我见过太多人写错。2.4 无穷大的选取有讲究INF不能随便设。如果设成INT_MAX那么dist[u]w就可能溢出变成负数导致更新逻辑出错。常见做法是设成0x3f3f3f3f这个值大约是10亿两个相加不会溢出int而且足够大能表示“不可达”。const int INF 0x3f3f3f3f;如果你用的是long long可以设成0x3f3f3f3f3f3f3f3f。这个技巧在竞赛圈里几乎是标配新手很容易忽略。3. 完整实操过程与代码实现3.1 题目建模把“花费”翻译成图假设题目描述是这样的有n个城市m条道路每条道路有一个过路费。求从城市1到城市n的最小总花费。建模过程城市 → 图的节点编号1到n。道路 → 图的边无向边就存两次有向边存一次。过路费 → 边的权重w。起点 → 节点1终点 → 节点n。如果题目问的是“从起点到所有点的最小花费”那就输出整个dist数组。如果只问终点就输出dist[n]。3.2 输入处理与建图#include bits/stdc.h using namespace std; const int MAXN 100005; const int INF 0x3f3f3f3f; vectorpairint,int g[MAXN]; int dist[MAXN]; int main() { int n, m, s, t; cin n m s t; for (int i 0; i m; i) { int u, v, w; cin u v w; g[u].push_back({v, w}); g[v].push_back({u, w}); // 无向图 } // Dijkstra memset(dist, 0x3f, sizeof(dist)); dist[s] 0; priority_queuepairint,int, vectorpairint,int, greater pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; for (auto [v, w] : g[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } if (dist[t] INF) cout -1 endl; else cout dist[t] endl; return 0; }这段代码可以直接抄去用。注意几个点无向图要存两次边输出前判断是否可达memset按字节赋值0x3f每个字节都是0x3f所以整个int就是0x3f3f3f3f。3.3 手动模拟一遍执行过程用一个具体例子走一遍加深理解。假设有4个点5条边1 --2-- 2 1 --5-- 3 2 --1-- 3 2 --3-- 4 3 --2-- 4求1到4的最小花费。初始化dist [0, INF, INF, INF]下标从1开始。第一轮取点1dist0。更新邻居dist[2]2dist[3]5。堆里有(2,2)、(5,3)。第二轮取点2dist2。更新邻居到3213 5dist[3]3到4235dist[4]5。堆里有(3,3)、(5,3旧)、(5,4)。第三轮取点3dist3。更新邻居到4325不小于dist[4]5不更新。堆里有(5,3旧)、(5,4)。第四轮取点3旧的dist5 当前dist[3]3跳过。取点4dist5结束。最终dist[4]5路径是1→2→4花费235。也可以走1→2→3→4花费2125一样。但1→3→4是527更贵。这个手动模拟能帮你确认代码逻辑是否正确。如果你写的代码跑出来不是5那就对照这个流程找问题。3.4 复杂度分析与数据范围匹配数据范围推荐写法复杂度n≤1000, m≤10000邻接矩阵朴素DijkstraO(n²)n≤10^5, m≤2×10^5邻接表堆优化O((nm)logn)n≤10^5, m≤2×10^5, 多组查询堆优化预处理视情况“最小花费”这类题如果n到了10^5级别朴素版必超时。我实测过n10000、m50000的时候朴素版跑一次大概0.3秒堆优化版只要0.01秒。差距非常明显。4. 常见问题与排查技巧实录4.1 为什么我的答案总是比正确答案大这是最常见的问题。原因通常有三个忘记处理重边两个点之间可能有多条边你只存了最后一条。解决办法是存边的时候不覆盖或者取最小值。用邻接表存所有边就不会有这个问题因为Dijkstra会自动选最小的那条。INF设得太小如果路径总花费超过了INF就会被误判为不可达。检查一下INF是否大于所有可能路径的最大值。无向图只存了一次边题目说“道路”通常是双向的只存u→v不存v→u会导致某些点不可达。4.2 堆优化版为什么会TLE堆优化版TLE通常是因为堆里元素太多。每次更新都push一个新元素最坏情况下堆的大小是O(m)。如果m10^6堆操作就会很慢。优化技巧可以用pair的默认比较但要注意greater的写法。另外如果同一个点的dist被多次更新可以只保留最新的但标准做法就是push后跳过过期元素这个开销是可以接受的。还有一种情况是用了cin/cout没关同步。数据量大的时候cin比scanf慢很多。加上这两行ios::sync_with_stdio(false); cin.tie(0);4.3 常见问题速查表现象可能原因排查方法答案偏大重边未处理、INF太小打印dist数组逐点检查答案偏小有负权边、更新条件写反确认边权非负、检查方向部分点不可达无向图只存单向、起点编号错检查建图代码、确认起点TLE用了朴素版、cin未关同步换堆优化、加sync_with_stdio段错误数组开小、越界访问检查MAXN是否够大死循环优先队列比较器写错确认是小根堆4.4 几个容易忽略的边界情况起点等于终点dist[s]0直接输出0。代码里不需要特判因为初始化就是0。图不连通终点不可达时输出-1或题目指定的值。不要直接输出INF。只有一个点m0循环不执行dist[s]0正确。自环u到u的边权重非负不会影响结果但会浪费一次更新。可以忽略。注意有些题目会问“最小花费”但边权是乘法关系比如汇率转换。这时候Dijkstra的贪心策略需要调整——因为乘法下“当前最小”不一定保证全局最优除非所有边权都大于1。遇到这种变形题要特别小心最好先确认边权性质。4.5 我踩过的三个坑第一个坑是memset(dist, 0x3f, sizeof(dist))写成了memset(dist, INF, sizeof(dist))。memset是按字节赋值的INF0x3f3f3f3f有四个字节memset只会取最低字节0x3f结果每个int变成0x3f3f3f3f看起来对了但如果INF定义成别的值就会出错。正确写法是memset(dist, 0x3f, sizeof(dist))。第二个坑是优先队列的比较器。priority_queuepairint,int默认按first从大到小排取出来的是最大值。必须写成greaterpairint,int才是小根堆。我有一次忘了加结果跑出来完全不对调试了半小时才发现。第三个坑是重边处理。有一次我用邻接矩阵存图读入边的时候直接g[u][v]w结果后面的边覆盖了前面的。如果后面的边权重更大就会漏掉更优的解。后来改成g[u][v]min(g[u][v], w)才过。5. 从这道题延伸出去的知识点5.1 记录路径怎么改有时候题目不只问最小花费还要输出走的哪条路。只需要加一个pre[]数组在更新dist的时候记录前驱节点if (dist[u] w dist[v]) { dist[v] dist[u] w; pre[v] u; pq.push({dist[v], v}); }最后从终点往回倒推就能得到完整路径。注意如果有多条最短路记录的是其中一条具体哪条取决于更新顺序。5.2 多源最短路怎么处理如果题目问“从任意一个起点出发到终点的最小花费”可以加一个虚拟源点把它到所有起点的边权设为0然后从虚拟源点跑一次Dijkstra。这个技巧在“最小花费”的变形题里很常见。5.3 边权是二维的怎么办有些题目的“花费”包含两个维度比如时间和金钱。如果要求“在时间不超过T的前提下花费最小”那就不是纯Dijkstra能解决的了需要用到分层图或者带约束的最短路。这种题一般会出现在进阶训练里基础阶段先把一维的练熟。5.4 和最小生成树的区别新手容易把最短路和最小生成树搞混。最短路是“从起点到终点的一条路径”最小生成树是“连接所有点的一棵树”。前者用Dijkstra后者用Kruskal或Prim。虽然都涉及“最小”但目标完全不同。判断方法很简单如果题目问“从A到B怎么走最省”是最短路如果问“把所有点连起来最少花多少”是最小生成树。我在实际写题的时候一般会先把Dijkstra的模板默写一遍确认没有笔误再开始改。模板这种东西写熟了就是肌肉记忆但隔一段时间不写就容易在细节上翻车。建议你也准备一份自己的模板每次写之前对照检查一遍关键点INF的值、优先队列的比较器、过期元素的跳过、无向图的双向存边。这四个地方不出错基本就能AC。
阅读完成 · 觉得有帮助？
