一说起单源最短路很多人脑子里第一个蹦出来的算法就是迪杰斯特拉Dijkstra。从1959年被提出到现在快七十年过去它在图论算法里依然保持着超高出场率。大多数人都是先背板子再用真正问到“朴素版、堆优化版、邻接表、链式前向星”这些变体反而容易绕晕。这篇文章我打算把几种最常见的写法一次性讲清楚朴素版配邻接矩阵、邻接表的两种建图、链式前向星建图以及堆优化版的核心逻辑。适合刚开始学最短路的新手也适合想在比赛前把板子彻底吃透、避免考场翻车的同学。先给个全局结论图的边数E接近V²时朴素版的空间和时间都不吃亏图特别稀疏时堆优化版本是首选存图方面vector邻接表写起来最舒服链式前向星看着吓人实际又稳又快是很多算法竞赛选手的默认姿势。下面逐个拆解代码统一用C写注释会尽量给足。1. 最短路径问题与Dijkstra的贪心根基1.1 要解决的是怎样一个问题迪杰斯特拉算法解决的是单源最短路给定一张带权图和一个起点s求s到其他所有顶点的最短距离。用导航类比最直观你从家到公司有多条路线每个路口是一个顶点每条路是一条带权边路口对路线的选择就是最短路计算。这种模型在社交网络、交通规划、电路设计里都能见到也是图论里最基础的一类优化问题。输入一般给的是顶点数n、边数m、每条边的起点u、终点v和权值w最后给一个起点s要求输出s到每个点的最短路长度。模板题通常长这样n个城市m条双向道路每条路有通行时间问你从1号城市到n号城市的最短时间——这就是最标准的单源最短路场景。理解这个问题时要抓住三个关键点第一路径允许经过任意多个中间点第二路径总长度是所有边权之和第三我们关心的是最小值而不是路径本身虽然要还原路径也有办法后面我在最后一节提一下。初学者最容易犯的一个毛病是看到“最短路”就急着搜索其实在带权图上用DFS全排列是灾难级的复杂度而Dijkstra能在多项式时间内解决这个问题靠的是下面这招贪心。1.2 贪心策略为什么成立以及它的前提条件Dijkstra的核心策略一句话就能说清每次从未确定最短路的点里挑一个当前dist最小的点u认为它的最短路已经确定然后用u去松弛它的所有邻居。这个“挑最小”的步骤就是贪心关键在于为什么挑出来的u就一定是最短路。证明用的反证法。假设当前未确定集合里dist最小的点u还存在另一条更短的路径到u那么这条路径离开“已确定集合”的第一个点一定是某个未确定点x。由于边权非负经过x绕到u的总长度至少是dist[x]而我们已经知道dist[x] ≥ dist[u]所以经过x的路径不可能比当前dist[u]更短。因此u的最短路确实已经找到了。整个证明最依赖的条件就是边权非负只要出现负权边这个推理当场失效。所以使用Dijkstra前必须先确认图上没有负权边。负权边会让“中途绕路”反而变短贪心选点就可能选错后面更新完发现某条路径更短时那个已经被标记确定的最短路就永远无法修正了。处理负权边需要换Bellman-Ford或者SPFA那是另一个话题不在本文范围。做题时如果题目没有明确说明边权非负可以先看一下数据范围大部分最短路模板题都会声明边权为正放心用Dijkstra就行。2. 朴素版Dijkstra最直觉的写法2.1 算法执行流程拆解朴素版Dijkstra是最接近算法思想的写法事情分成三步初始化、循环选点、松弛更新。第一步初始化dist数组。dist[s]0其余点都是INFINF要开得足够大一般习惯用0x3f3f3f3f大约10亿多既保证比所有合法路径大又不会在加法中溢出。同时准备一个vis数组记录每个点是否已经确定最短路。第二步循环n次。每次从所有“未访问且dist值最小”的点里找u把vis[u]设为true。这一步是朴素版的核心也是后面性能瓶颈的来源因为它根本没有用任何数据结构就是纯线性扫描。第三步遍历u的所有邻边进行松弛操作。松弛听起来玄乎其实就是比较如果dist[u]加上边权w比现在记录的dist[v]更小就更新dist[v]。用代码表达就是dist[v] min(dist[v], dist[u] w)。重复第二、三步n次后所有可达点的最短路就全部算完了。再把循环次数想清楚每次循环一定能让一个点被确定为最短路总共n个点所以外层循环n次就够。如果某次找u时所有未访问点距离都是INF说明剩下的点从s根本到不了直接break掉没必要继续空转这个小优化在多个孤立点的图上能省不少时间。2.2 朴素版完整代码邻接矩阵版题目给的是稠密图时邻接矩阵是最方便的存图方式。g[u][v]直接存u到v的边权没有边就是INF自己到自己是0。下面代码我按1到n的编号写这样下标不容易错。#include bits/stdc.h using namespace std; const int MAXN 1005; const int INF 0x3f3f3f3f; int n, m, s; int g[MAXN][MAXN]; int dist[MAXN]; bool vis[MAXN]; void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); memset(vis, false, sizeof(vis)); dist[s] 0; for (int i 1; i n; i) { // 1. 找未确定最短路且dist最小的点 int u -1, minD INF; for (int j 1; j n; j) { if (!vis[j] dist[j] minD) { minD dist[j]; u j; } } // 剩下的点都不可达 if (u -1) break; // 2. 标记u已确定 vis[u] true; // 3. 松弛u的所有出边 for (int v 1; v n; v) { if (!vis[v] g[u][v] ! INF) { dist[v] min(dist[v], dist[u] g[u][v]); } } } } int main() { scanf(%d%d%d, n, m, s); memset(g, 0x3f, sizeof(g)); for (int i 1; i n; i) g[i][i] 0; for (int i 0; i m; i) { int u, v, w; scanf(%d%d%d, u, v, w); g[u][v] min(g[u][v], w); // 重边时保留最小权 // 如果是无向图再加一行 g[v][u] min(g[v][u], w); } dijkstra(s); for (int i 1; i n; i) { printf(%d%c, dist[i], i n ? \n : ); } return 0; }写代码时有两个细节值得提。第一初始化邻接矩阵之前别忘把g全部置INF再把对角线设成0否则一个点自己到自己会算出错误结果。第二输入如果存在重边直接取最小值这是最稳妥的处理方式不然后面松弛时用的是较大边权答案就偏了。2.3 朴素版的复杂度与适用边界朴素版的时间复杂度是O(V² E)其中V是顶点数E是边数。每次选点要扫一遍所有点共V轮总共V²的代价所有边的松弛合起来是E。因为邻接矩阵里E本身可以做到V²量级所以总复杂度常被直接记为O(V²)。空间上邻接矩阵是V²n上万时直接内存爆掉。用朴素版最舒服的场景是稠密图加小数据范围比如n ≤ 2000边数几乎拉满用邻接矩阵简单直接代码短不容易出错。如果n到了10⁵这个量级光是二维数组开不下而且每次线性选点的V²操作也完全跑不动这时候就必须上堆优化和更省内存的存图方式了。3. 存图方式邻接表与链式前向星的抉择3.1 vector邻接表简单直观的第一选择邻接表的思路很朴素把每个点的出边存到一个列表里存图时只记录实际存在的边省掉了邻接矩阵浪费在“无边”位置上的空间。用C的vector实现几乎不需要动脑一个结构体Edge包含to和w然后开一个vector g[MAXN]就行。struct Edge { int to, w; }; vectorEdge g[MAXN]; void addEdge(int u, int v, int w) { g[u].push_back({v, w}); // 无向图就再 push_back({u, w}) }遍历某个点u的所有邻居时直接for (auto e : g[u])拿到的e.to和e.w就是边的终点和权值。这种写法的优势是代码可读性极好调试也方便我给别人讲Dijkstra时第一步都是先让他用vector写等把算法本身吃透了再去碰链式前向星。代价也是存在的vector在插入时会涉及动态扩容虽然均摊下来没问题但大量建图时频繁分配内存会带来额外开销另外对于每个点存的是一个个对象在某些极端数据下cache局部性不如连续数组好。对工程开发来说这点开销几乎不用在意但竞赛里有人就是喜欢把每一毫秒都抠出来。3.2 链式前向星看着复杂用起来真香链式前向星本质上还是邻接表只是用数组模拟“链表”来存边。每个点有一个head[u]代表这个点第一条边在边数组里的下标每条边的next字段指向同一起点的下一条边的下标。有点像按头插法建的单链表只不过节点不是malloc出来的而是提前开好的结构体数组。struct Edge { int to, w, next; } e[MAXN 1]; // 无向图边的数量要开2倍 int head[MAXN], cnt 0; void addEdge(int u, int v, int w) { e[cnt] {v, w, head[u]}; head[u] cnt; }初次接触的人常常看不懂赋值的顺序我拆开说。e[cnt]表示先用新边槽位然后to和w存终点和权值next存的是旧的head[u]也就是u原来的第一条边再把head[u]指向新边的下标cnt。于是从head[u]出发沿着next一路走下去就能遍历到u的每条出边遍历顺序和插入顺序正好相反也就是后加的边反而先被访问到。遍历代码写成这样for (int i head[u]; i ! 0; i e[i].next) { int v e[i].to; int w e[i].w; // 处理边(u, v) }为什么终止条件是i ! 0因为head数组初始化为0当某条边的next指向0时说明它已经是链尾了。注意边下标从1开始0被留作空标记这样实现非常巧妙把所有边界情况都统一成了“遇到0就停”。用数组模拟链表的好处是内存连续、分配固定、没有vector的动态扩容遍历时性能非常稳定。另一个隐藏优势是边是有“编号”的后面如果想做最大流、最小费用流等进阶算法需要记录反向边编号链式前向星一套就解决了vector则需要额外存下标。3.3 两种存图方式怎么选很多初学者会纠结到底学哪种我的建议是看你的目标。如果是为了快速理解算法、写作业、做项目vector邻接表完全够了代码量小出bug的概率低。如果打算法竞赛或者以后要碰网络流、分层图这些进阶内容链式前向星尽早熟练起来它是目前竞赛圈最通用的存图范式几乎所有的Dijkstra、SPFA、最大流板子都用它写网上题解你看多了之后会发现这个结构出现频率极高。二者在Dijkstra里的区别其实没有想象中大堆优化版配vector也能过大多数题目。存图方式只是基本功真正决定算法效率的是下面这个优化。4. 堆优化Dijkstra让大规模图跑起来4.1 朴素版慢在哪里回顾朴素版的两大开销找最小点的O(V²)以及松弛边的O(E)。当图稀疏时E只是V的常数倍但选点还是要V²这就显得很亏。能不能把“找最小点”这一步用更快的结构替代答案是可以用优先队列堆来维护当前所有“待确定点”的dist取最小值就从O(V)变成了O(1)插入和更新则变成了O(log V)。代价是每次dist更新时都要往堆里塞一个新记录所以堆里会出现同一个点的多个“过期版本”我们用vis数组在弹出时判断即可。这种“堆里可能有过期数据弹出时发现已访问就丢弃”的做法常常被称为懒删除它比手动实现decrease-key简单太多性能上也够用。你要真去手写一个支持改堆内元素值的二叉堆代码量翻倍不说还极易写错得不偿失。4.2 优先队列加链式前向星的完整实现堆优化版Dijkstra的流程我已经写成下面这份完整代码展开说。#include bits/stdc.h using namespace std; const int MAXN 100005; const int MAXM 200005; const int INF 0x3f3f3f3f; struct Edge { int to, w, next; } e[MAXM]; int head[MAXN], cnt 0; void addEdge(int u, int v, int w) { e[cnt] {v, w, head[u]}; head[u] cnt; } int dist[MAXN]; bool vis[MAXN]; struct Node { int u, d; bool operator(const Node other) const { return d other.d; // 小顶堆priority_queue默认是大顶堆反着写 } }; void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); memset(vis, false, sizeof(vis)); dist[s] 0; priority_queueNode pq; pq.push({s, 0}); while (!pq.empty()) { Node cur pq.top(); pq.pop(); int u cur.u; if (vis[u]) continue; // 过期记录直接丢掉 vis[u] true; for (int i head[u]; i ! 0; i e[i].next) { int v e[i].to; int w e[i].w; if (!vis[v] dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({v, dist[v]}); } } } }用pairint,int写还能更短一点first存距离second存编号默认按first排序配合greater即可priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (vis[u]) continue; vis[u] true; for (int i head[u]; i; i e[i].next) { int v e[i].to, w e[i].w; if (dist[v] d w) { dist[v] d w; pq.push({dist[v], v}); } } }这段代码更适合在OJ上快速敲板子用C17的结构化绑定让代码很清爽。两种写法等价我个人习惯用结构体版本因为语义更清楚想要扩展维护路径时也方便。4.3 堆优化的复杂度到底是多少堆优化后每次push和pop都是O(log V)最坏情况下每条边都可能触发一次push因此总复杂度是O((V E) log V)。在稀疏图中E约等于V量级总代价接近于O(V log V)比朴素版的O(V²)快出好几个数量级。举个例子n 10⁵m 2×10⁵的稀疏图堆优化轻松跑完朴素版连矩阵都开不下。不过这并不代表堆优化永远碾压朴素版。当图特别稠密E接近V²时log因子会让堆优化的常数偏大朴素版的V²反而更有竞争力。看着矛盾其实核心是选合适的工具而不是认一个写法走天下。4.4 邻接表加堆优化的写法有人觉得链式前向星门槛高先用vector邻接表加堆优化也没问题。只需要把上一节代码里的遍历部分换成vector遍历即可算法主体完全一样。我建议初学者这样练一遍先用vector写通再改成链式前向星对比两份代码的差异你会理解得特别透彻。下面这个片段展示关键差异for (auto e : g[u]) { int v e.to, w e.w; if (!vis[v] dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({v, dist[v]}); } }你看和链式前向星的区别只是遍历方式其余完全一致。所以存图方式和优化策略是两件事别把它们搅在一起。5. 新手最容易踩的五个坑附排查思路5.1 初始化写漏dist、vis全是脏数据memset(dist, 0x3f, sizeof(dist))这个写法为什么很多人爱用因为0x3f3f3f3f按字节填充后每个int正好是0x3f3f3f3f而且memset对所有数组统一生效一行搞定。但有人会漏掉初始化vis导致上次数据残留跑出来的答案极其诡异。我调试过的最常见错误就是第二组样例沿用上一组数据的vis状态结果该访问的点被跳过dist到处乱飞。排查办法很简单每次算法开始前代码里第一件事就是两个memset并且养成“写完函数先看初始化”的习惯。如果题目多组输入更要注意这一点组与组之间的全局数组必须重置干净。5.2 INF设得太小加法直接溢出INF如果设成10⁹两个INF相加就是2×10⁹虽然还在int范围内但再加一点边权就溢出了会变成负数然后这个负数更小继续传播dist数组彻底被污染。这就是为什么我强烈推荐0x3f3f3f3f它的值约1.06×10⁹两个相加约2.1×10⁹仍在int可表示范围内不会变成负数同时它又足够大任何合法最短路都不会超过这个值。千万避免用INT_MAX当INF一旦执行dist[u] w立即溢出成未定义行为。比赛中这种bug很难肉眼发现因为答案看起来只是“怪怪的”。如果你发现输出里有莫名其妙的负数先检查INF和相关加法。5.3 重边和自环的处理重边就是两个点之间存在多条边权值不同。朴素版邻接矩阵实现里直接取最小权存进去即可vector邻接表和链式前向星不需要特殊处理因为松弛时会自动比较多条边都会被遍历到更新次数多一点但不影响正确性。自环更不用慌权值非负的情况下dist[u] w永远不小于dist[u]自环不会被采纳算法自然免疫。真正要小心的是无向边开数组大小的问题。链式前向星每加一条无向边要addEdge两次如果题目给出的是m条无向边边数组要开2m少开一个就数组越界表现形式可能是答案不对、随机崩溃非常难受。建完图后可以加个断言看cnt有没有超过边数组上限或者干脆养成“无向边开2倍网络流开4倍”的肌肉记忆。5.4 优先队列比较器写反priority_queue默认是大顶堆取出的距离值是最大的这显然是错的。用自定义结构体时比较函数里的号写成号就会变成大顶堆所有“最短”逻辑全部逆转。用pairint,int时加上greater即可构造小顶堆。这个坑几乎人人踩过不是新手专属我见过比赛时候写错导致WA的也不是一次两次了。判断比较器是否正确有一个小技巧打印堆顶距离看是不是从0开始逐渐增大的。如果第一次取出的是很大的数比较器必定写反了。养成这个习惯后一眼就能定位。5.5 多组数据、边界数据怎么自测调Dijkstra的最有效方法不是对着样例看而是写一个暴力对拍。写一个复杂度很高的朴素版或者DFS暴力算最短路然后生成随机小数据同时喂给两份代码比较输出是否一致。一旦不一致立刻把导致差异的数据缩小到几个点用debug输出逐行跟踪。这种对拍方法几乎适用于一切算法题我学图论时最受益的技巧就是这个。手工构造几个极简图也很管用一个孤立点、一条长链、全是重边的图、起点到不了的图、完全图每个边界都跑一遍正确性就有了基本保障。6. 实战选型建议与一点扩展心得6.1 朴素版还是堆优化到底怎么选先看数据范围再动手。n ≤ 10³到10⁴且m接近n²时邻接矩阵加朴素版最稳代码短不容易写错而且数据量小根本不差这点运行时间。n ≥ 10⁵量级几乎无脑堆优化加链式前向星这时候朴素版不是“慢一点”的问题而是内存和复杂度双重爆炸。如果题目没给明确说明按最坏情况估计默认堆优化。因为它能覆盖更大范围的题目代码也就比朴素版多十几行熟练后反而觉得更顺手。考试时间紧的时候我会先花十秒钟判断数据规模再决定抄哪份板子基本不会因为选错板子而栽跟头。6.2 链式前向星比vector多出来的隐藏价值很多人以为选链式前向星只是为了性能其实它更大的价值在于扩展性。边有了编号反向边的编号可以通过^1快速得到这在最大流算法里是刚需分层图、最短路径树、严格次短路等问题的实现也常常基于边的编号做各种操作。vector虽然也能存下标但链式前向星的写法在代码层面更接近传统邻接表后续学高级算法时几乎零迁移成本。另外链式前向星的遍历是在连续数组上跑的cache命中率比存储松散的对象vector更好这在数据量极大时会有可感知的差距。加上它不需要动态扩容、内存使用精确可控竞赛里优势确实实实在在。6.3 最后分享一个关于记录路径的心得我们上面只求了最短距离但很多题会要求输出路径。做法很简单新增一个pre数组松弛成功时记录pre[v] u最后从终点沿着pre一路回溯到起点再把序列反转输出即可。这里有个小坑如果用的是堆优化注意只应该在真正更新dist时修改pre不要拿过期的堆记录去覆盖pre。保持“松弛成功才记录”这个原则路径就一定是对的。我一开始在这里吃过亏后来把更新逻辑整理成三步比较、赋值、记录再也没有错过。我个人实际用下来的体会是Dijkstra这套算法强在思想简单、板子统一真正难的是在变式题里把它认出来。多刷几道网格图、分层图、带限制的最短路题后你会发现核心永远还是那个贪心选点加松弛的框架所有优化和存图技巧都服务于一句话让每次选点更快让每次松弛更高效。把这套组合拳练熟遇到再复杂的最短路变化心里都不虚。 
长河君 · 2026/10/16 1:17:14 · 阅读 1.2k 单源最短路Dijkstra全解：朴素版、堆优化与链式前向星实现
一说起单源最短路很多人脑子里第一个蹦出来的算法就是迪杰斯特拉Dijkstra。从1959年被提出到现在快七十年过去它在图论算法里依然保持着超高出场率。大多数人都是先背板子再用真正问到“朴素版、堆优化版、邻接表、链式前向星”这些变体反而容易绕晕。这篇文章我打算把几种最常见的写法一次性讲清楚朴素版配邻接矩阵、邻接表的两种建图、链式前向星建图以及堆优化版的核心逻辑。适合刚开始学最短路的新手也适合想在比赛前把板子彻底吃透、避免考场翻车的同学。先给个全局结论图的边数E接近V²时朴素版的空间和时间都不吃亏图特别稀疏时堆优化版本是首选存图方面vector邻接表写起来最舒服链式前向星看着吓人实际又稳又快是很多算法竞赛选手的默认姿势。下面逐个拆解代码统一用C写注释会尽量给足。1. 最短路径问题与Dijkstra的贪心根基1.1 要解决的是怎样一个问题迪杰斯特拉算法解决的是单源最短路给定一张带权图和一个起点s求s到其他所有顶点的最短距离。用导航类比最直观你从家到公司有多条路线每个路口是一个顶点每条路是一条带权边路口对路线的选择就是最短路计算。这种模型在社交网络、交通规划、电路设计里都能见到也是图论里最基础的一类优化问题。输入一般给的是顶点数n、边数m、每条边的起点u、终点v和权值w最后给一个起点s要求输出s到每个点的最短路长度。模板题通常长这样n个城市m条双向道路每条路有通行时间问你从1号城市到n号城市的最短时间——这就是最标准的单源最短路场景。理解这个问题时要抓住三个关键点第一路径允许经过任意多个中间点第二路径总长度是所有边权之和第三我们关心的是最小值而不是路径本身虽然要还原路径也有办法后面我在最后一节提一下。初学者最容易犯的一个毛病是看到“最短路”就急着搜索其实在带权图上用DFS全排列是灾难级的复杂度而Dijkstra能在多项式时间内解决这个问题靠的是下面这招贪心。1.2 贪心策略为什么成立以及它的前提条件Dijkstra的核心策略一句话就能说清每次从未确定最短路的点里挑一个当前dist最小的点u认为它的最短路已经确定然后用u去松弛它的所有邻居。这个“挑最小”的步骤就是贪心关键在于为什么挑出来的u就一定是最短路。证明用的反证法。假设当前未确定集合里dist最小的点u还存在另一条更短的路径到u那么这条路径离开“已确定集合”的第一个点一定是某个未确定点x。由于边权非负经过x绕到u的总长度至少是dist[x]而我们已经知道dist[x] ≥ dist[u]所以经过x的路径不可能比当前dist[u]更短。因此u的最短路确实已经找到了。整个证明最依赖的条件就是边权非负只要出现负权边这个推理当场失效。所以使用Dijkstra前必须先确认图上没有负权边。负权边会让“中途绕路”反而变短贪心选点就可能选错后面更新完发现某条路径更短时那个已经被标记确定的最短路就永远无法修正了。处理负权边需要换Bellman-Ford或者SPFA那是另一个话题不在本文范围。做题时如果题目没有明确说明边权非负可以先看一下数据范围大部分最短路模板题都会声明边权为正放心用Dijkstra就行。2. 朴素版Dijkstra最直觉的写法2.1 算法执行流程拆解朴素版Dijkstra是最接近算法思想的写法事情分成三步初始化、循环选点、松弛更新。第一步初始化dist数组。dist[s]0其余点都是INFINF要开得足够大一般习惯用0x3f3f3f3f大约10亿多既保证比所有合法路径大又不会在加法中溢出。同时准备一个vis数组记录每个点是否已经确定最短路。第二步循环n次。每次从所有“未访问且dist值最小”的点里找u把vis[u]设为true。这一步是朴素版的核心也是后面性能瓶颈的来源因为它根本没有用任何数据结构就是纯线性扫描。第三步遍历u的所有邻边进行松弛操作。松弛听起来玄乎其实就是比较如果dist[u]加上边权w比现在记录的dist[v]更小就更新dist[v]。用代码表达就是dist[v] min(dist[v], dist[u] w)。重复第二、三步n次后所有可达点的最短路就全部算完了。再把循环次数想清楚每次循环一定能让一个点被确定为最短路总共n个点所以外层循环n次就够。如果某次找u时所有未访问点距离都是INF说明剩下的点从s根本到不了直接break掉没必要继续空转这个小优化在多个孤立点的图上能省不少时间。2.2 朴素版完整代码邻接矩阵版题目给的是稠密图时邻接矩阵是最方便的存图方式。g[u][v]直接存u到v的边权没有边就是INF自己到自己是0。下面代码我按1到n的编号写这样下标不容易错。#include bits/stdc.h using namespace std; const int MAXN 1005; const int INF 0x3f3f3f3f; int n, m, s; int g[MAXN][MAXN]; int dist[MAXN]; bool vis[MAXN]; void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); memset(vis, false, sizeof(vis)); dist[s] 0; for (int i 1; i n; i) { // 1. 找未确定最短路且dist最小的点 int u -1, minD INF; for (int j 1; j n; j) { if (!vis[j] dist[j] minD) { minD dist[j]; u j; } } // 剩下的点都不可达 if (u -1) break; // 2. 标记u已确定 vis[u] true; // 3. 松弛u的所有出边 for (int v 1; v n; v) { if (!vis[v] g[u][v] ! INF) { dist[v] min(dist[v], dist[u] g[u][v]); } } } } int main() { scanf(%d%d%d, n, m, s); memset(g, 0x3f, sizeof(g)); for (int i 1; i n; i) g[i][i] 0; for (int i 0; i m; i) { int u, v, w; scanf(%d%d%d, u, v, w); g[u][v] min(g[u][v], w); // 重边时保留最小权 // 如果是无向图再加一行 g[v][u] min(g[v][u], w); } dijkstra(s); for (int i 1; i n; i) { printf(%d%c, dist[i], i n ? \n : ); } return 0; }写代码时有两个细节值得提。第一初始化邻接矩阵之前别忘把g全部置INF再把对角线设成0否则一个点自己到自己会算出错误结果。第二输入如果存在重边直接取最小值这是最稳妥的处理方式不然后面松弛时用的是较大边权答案就偏了。2.3 朴素版的复杂度与适用边界朴素版的时间复杂度是O(V² E)其中V是顶点数E是边数。每次选点要扫一遍所有点共V轮总共V²的代价所有边的松弛合起来是E。因为邻接矩阵里E本身可以做到V²量级所以总复杂度常被直接记为O(V²)。空间上邻接矩阵是V²n上万时直接内存爆掉。用朴素版最舒服的场景是稠密图加小数据范围比如n ≤ 2000边数几乎拉满用邻接矩阵简单直接代码短不容易出错。如果n到了10⁵这个量级光是二维数组开不下而且每次线性选点的V²操作也完全跑不动这时候就必须上堆优化和更省内存的存图方式了。3. 存图方式邻接表与链式前向星的抉择3.1 vector邻接表简单直观的第一选择邻接表的思路很朴素把每个点的出边存到一个列表里存图时只记录实际存在的边省掉了邻接矩阵浪费在“无边”位置上的空间。用C的vector实现几乎不需要动脑一个结构体Edge包含to和w然后开一个vector g[MAXN]就行。struct Edge { int to, w; }; vectorEdge g[MAXN]; void addEdge(int u, int v, int w) { g[u].push_back({v, w}); // 无向图就再 push_back({u, w}) }遍历某个点u的所有邻居时直接for (auto e : g[u])拿到的e.to和e.w就是边的终点和权值。这种写法的优势是代码可读性极好调试也方便我给别人讲Dijkstra时第一步都是先让他用vector写等把算法本身吃透了再去碰链式前向星。代价也是存在的vector在插入时会涉及动态扩容虽然均摊下来没问题但大量建图时频繁分配内存会带来额外开销另外对于每个点存的是一个个对象在某些极端数据下cache局部性不如连续数组好。对工程开发来说这点开销几乎不用在意但竞赛里有人就是喜欢把每一毫秒都抠出来。3.2 链式前向星看着复杂用起来真香链式前向星本质上还是邻接表只是用数组模拟“链表”来存边。每个点有一个head[u]代表这个点第一条边在边数组里的下标每条边的next字段指向同一起点的下一条边的下标。有点像按头插法建的单链表只不过节点不是malloc出来的而是提前开好的结构体数组。struct Edge { int to, w, next; } e[MAXN 1]; // 无向图边的数量要开2倍 int head[MAXN], cnt 0; void addEdge(int u, int v, int w) { e[cnt] {v, w, head[u]}; head[u] cnt; }初次接触的人常常看不懂赋值的顺序我拆开说。e[cnt]表示先用新边槽位然后to和w存终点和权值next存的是旧的head[u]也就是u原来的第一条边再把head[u]指向新边的下标cnt。于是从head[u]出发沿着next一路走下去就能遍历到u的每条出边遍历顺序和插入顺序正好相反也就是后加的边反而先被访问到。遍历代码写成这样for (int i head[u]; i ! 0; i e[i].next) { int v e[i].to; int w e[i].w; // 处理边(u, v) }为什么终止条件是i ! 0因为head数组初始化为0当某条边的next指向0时说明它已经是链尾了。注意边下标从1开始0被留作空标记这样实现非常巧妙把所有边界情况都统一成了“遇到0就停”。用数组模拟链表的好处是内存连续、分配固定、没有vector的动态扩容遍历时性能非常稳定。另一个隐藏优势是边是有“编号”的后面如果想做最大流、最小费用流等进阶算法需要记录反向边编号链式前向星一套就解决了vector则需要额外存下标。3.3 两种存图方式怎么选很多初学者会纠结到底学哪种我的建议是看你的目标。如果是为了快速理解算法、写作业、做项目vector邻接表完全够了代码量小出bug的概率低。如果打算法竞赛或者以后要碰网络流、分层图这些进阶内容链式前向星尽早熟练起来它是目前竞赛圈最通用的存图范式几乎所有的Dijkstra、SPFA、最大流板子都用它写网上题解你看多了之后会发现这个结构出现频率极高。二者在Dijkstra里的区别其实没有想象中大堆优化版配vector也能过大多数题目。存图方式只是基本功真正决定算法效率的是下面这个优化。4. 堆优化Dijkstra让大规模图跑起来4.1 朴素版慢在哪里回顾朴素版的两大开销找最小点的O(V²)以及松弛边的O(E)。当图稀疏时E只是V的常数倍但选点还是要V²这就显得很亏。能不能把“找最小点”这一步用更快的结构替代答案是可以用优先队列堆来维护当前所有“待确定点”的dist取最小值就从O(V)变成了O(1)插入和更新则变成了O(log V)。代价是每次dist更新时都要往堆里塞一个新记录所以堆里会出现同一个点的多个“过期版本”我们用vis数组在弹出时判断即可。这种“堆里可能有过期数据弹出时发现已访问就丢弃”的做法常常被称为懒删除它比手动实现decrease-key简单太多性能上也够用。你要真去手写一个支持改堆内元素值的二叉堆代码量翻倍不说还极易写错得不偿失。4.2 优先队列加链式前向星的完整实现堆优化版Dijkstra的流程我已经写成下面这份完整代码展开说。#include bits/stdc.h using namespace std; const int MAXN 100005; const int MAXM 200005; const int INF 0x3f3f3f3f; struct Edge { int to, w, next; } e[MAXM]; int head[MAXN], cnt 0; void addEdge(int u, int v, int w) { e[cnt] {v, w, head[u]}; head[u] cnt; } int dist[MAXN]; bool vis[MAXN]; struct Node { int u, d; bool operator(const Node other) const { return d other.d; // 小顶堆priority_queue默认是大顶堆反着写 } }; void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); memset(vis, false, sizeof(vis)); dist[s] 0; priority_queueNode pq; pq.push({s, 0}); while (!pq.empty()) { Node cur pq.top(); pq.pop(); int u cur.u; if (vis[u]) continue; // 过期记录直接丢掉 vis[u] true; for (int i head[u]; i ! 0; i e[i].next) { int v e[i].to; int w e[i].w; if (!vis[v] dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({v, dist[v]}); } } } }用pairint,int写还能更短一点first存距离second存编号默认按first排序配合greater即可priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (vis[u]) continue; vis[u] true; for (int i head[u]; i; i e[i].next) { int v e[i].to, w e[i].w; if (dist[v] d w) { dist[v] d w; pq.push({dist[v], v}); } } }这段代码更适合在OJ上快速敲板子用C17的结构化绑定让代码很清爽。两种写法等价我个人习惯用结构体版本因为语义更清楚想要扩展维护路径时也方便。4.3 堆优化的复杂度到底是多少堆优化后每次push和pop都是O(log V)最坏情况下每条边都可能触发一次push因此总复杂度是O((V E) log V)。在稀疏图中E约等于V量级总代价接近于O(V log V)比朴素版的O(V²)快出好几个数量级。举个例子n 10⁵m 2×10⁵的稀疏图堆优化轻松跑完朴素版连矩阵都开不下。不过这并不代表堆优化永远碾压朴素版。当图特别稠密E接近V²时log因子会让堆优化的常数偏大朴素版的V²反而更有竞争力。看着矛盾其实核心是选合适的工具而不是认一个写法走天下。4.4 邻接表加堆优化的写法有人觉得链式前向星门槛高先用vector邻接表加堆优化也没问题。只需要把上一节代码里的遍历部分换成vector遍历即可算法主体完全一样。我建议初学者这样练一遍先用vector写通再改成链式前向星对比两份代码的差异你会理解得特别透彻。下面这个片段展示关键差异for (auto e : g[u]) { int v e.to, w e.w; if (!vis[v] dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({v, dist[v]}); } }你看和链式前向星的区别只是遍历方式其余完全一致。所以存图方式和优化策略是两件事别把它们搅在一起。5. 新手最容易踩的五个坑附排查思路5.1 初始化写漏dist、vis全是脏数据memset(dist, 0x3f, sizeof(dist))这个写法为什么很多人爱用因为0x3f3f3f3f按字节填充后每个int正好是0x3f3f3f3f而且memset对所有数组统一生效一行搞定。但有人会漏掉初始化vis导致上次数据残留跑出来的答案极其诡异。我调试过的最常见错误就是第二组样例沿用上一组数据的vis状态结果该访问的点被跳过dist到处乱飞。排查办法很简单每次算法开始前代码里第一件事就是两个memset并且养成“写完函数先看初始化”的习惯。如果题目多组输入更要注意这一点组与组之间的全局数组必须重置干净。5.2 INF设得太小加法直接溢出INF如果设成10⁹两个INF相加就是2×10⁹虽然还在int范围内但再加一点边权就溢出了会变成负数然后这个负数更小继续传播dist数组彻底被污染。这就是为什么我强烈推荐0x3f3f3f3f它的值约1.06×10⁹两个相加约2.1×10⁹仍在int可表示范围内不会变成负数同时它又足够大任何合法最短路都不会超过这个值。千万避免用INT_MAX当INF一旦执行dist[u] w立即溢出成未定义行为。比赛中这种bug很难肉眼发现因为答案看起来只是“怪怪的”。如果你发现输出里有莫名其妙的负数先检查INF和相关加法。5.3 重边和自环的处理重边就是两个点之间存在多条边权值不同。朴素版邻接矩阵实现里直接取最小权存进去即可vector邻接表和链式前向星不需要特殊处理因为松弛时会自动比较多条边都会被遍历到更新次数多一点但不影响正确性。自环更不用慌权值非负的情况下dist[u] w永远不小于dist[u]自环不会被采纳算法自然免疫。真正要小心的是无向边开数组大小的问题。链式前向星每加一条无向边要addEdge两次如果题目给出的是m条无向边边数组要开2m少开一个就数组越界表现形式可能是答案不对、随机崩溃非常难受。建完图后可以加个断言看cnt有没有超过边数组上限或者干脆养成“无向边开2倍网络流开4倍”的肌肉记忆。5.4 优先队列比较器写反priority_queue默认是大顶堆取出的距离值是最大的这显然是错的。用自定义结构体时比较函数里的号写成号就会变成大顶堆所有“最短”逻辑全部逆转。用pairint,int时加上greater即可构造小顶堆。这个坑几乎人人踩过不是新手专属我见过比赛时候写错导致WA的也不是一次两次了。判断比较器是否正确有一个小技巧打印堆顶距离看是不是从0开始逐渐增大的。如果第一次取出的是很大的数比较器必定写反了。养成这个习惯后一眼就能定位。5.5 多组数据、边界数据怎么自测调Dijkstra的最有效方法不是对着样例看而是写一个暴力对拍。写一个复杂度很高的朴素版或者DFS暴力算最短路然后生成随机小数据同时喂给两份代码比较输出是否一致。一旦不一致立刻把导致差异的数据缩小到几个点用debug输出逐行跟踪。这种对拍方法几乎适用于一切算法题我学图论时最受益的技巧就是这个。手工构造几个极简图也很管用一个孤立点、一条长链、全是重边的图、起点到不了的图、完全图每个边界都跑一遍正确性就有了基本保障。6. 实战选型建议与一点扩展心得6.1 朴素版还是堆优化到底怎么选先看数据范围再动手。n ≤ 10³到10⁴且m接近n²时邻接矩阵加朴素版最稳代码短不容易写错而且数据量小根本不差这点运行时间。n ≥ 10⁵量级几乎无脑堆优化加链式前向星这时候朴素版不是“慢一点”的问题而是内存和复杂度双重爆炸。如果题目没给明确说明按最坏情况估计默认堆优化。因为它能覆盖更大范围的题目代码也就比朴素版多十几行熟练后反而觉得更顺手。考试时间紧的时候我会先花十秒钟判断数据规模再决定抄哪份板子基本不会因为选错板子而栽跟头。6.2 链式前向星比vector多出来的隐藏价值很多人以为选链式前向星只是为了性能其实它更大的价值在于扩展性。边有了编号反向边的编号可以通过^1快速得到这在最大流算法里是刚需分层图、最短路径树、严格次短路等问题的实现也常常基于边的编号做各种操作。vector虽然也能存下标但链式前向星的写法在代码层面更接近传统邻接表后续学高级算法时几乎零迁移成本。另外链式前向星的遍历是在连续数组上跑的cache命中率比存储松散的对象vector更好这在数据量极大时会有可感知的差距。加上它不需要动态扩容、内存使用精确可控竞赛里优势确实实实在在。6.3 最后分享一个关于记录路径的心得我们上面只求了最短距离但很多题会要求输出路径。做法很简单新增一个pre数组松弛成功时记录pre[v] u最后从终点沿着pre一路回溯到起点再把序列反转输出即可。这里有个小坑如果用的是堆优化注意只应该在真正更新dist时修改pre不要拿过期的堆记录去覆盖pre。保持“松弛成功才记录”这个原则路径就一定是对的。我一开始在这里吃过亏后来把更新逻辑整理成三步比较、赋值、记录再也没有错过。我个人实际用下来的体会是Dijkstra这套算法强在思想简单、板子统一真正难的是在变式题里把它认出来。多刷几道网格图、分层图、带限制的最短路题后你会发现核心永远还是那个贪心选点加松弛的框架所有优化和存图技巧都服务于一句话让每次选点更快让每次松弛更高效。把这套组合拳练熟遇到再复杂的最短路变化心里都不虚。