最早我写最短路的时候第一反应总是随手跑一遍类 Floyd 的三重循环图小的时候确实没毛病直到数据规模涨上来点一多、边一密朴素多源算法的三层循环直接被测评数据打回原形。这时候不得不老老实实把迪杰斯特拉捡起来从朴素版一路写到堆优化再折腾邻接表和链式前向星存图。标题里这四个关键词翻译过来其实是一条完整的进阶路线先让思路能跑通再让算法跑得快最后让代码在极限数据下不爆内存、不卡常数。这篇文章适合几类人刚学图论但被各种最短路题搞晕的初学者准备算法竞赛、面试手写代码需要一套放心模板的选手以及业务里需要自己实现路径规划、路由计算不想依赖重型框架的开发者。我尽量不只给模板而是把每个环节背后的“为什么”也讲清楚因为你只有理解了每一步的用意遇到变形题、调参题才不会慌。1. 最短路问题的边界迪杰斯特拉凭什么能“贪”出一条最短路径1.1 先搞清楚这张图里到底在算什么给定一张带权图边的权值可能来自距离、时间、花销也可能来自网络跳数、传输延迟。所谓单源最短路就是固定一个起点 s求出 s 到其他所有点的最短距离。地图导航、计算中心机房到各节点的网络延迟、配送路径规划这些场景抽出来都是同一个模型。迪杰斯特拉处理的是边权非负的单源最短路。注意“非负”是硬前提包括 0 权边但不包括负权边。几乎所有入门最短路题都满足这个条件所以它是一个极其通用的基础工具。算法输入三样东西点的数量 n、边的集合、起点 s。输出一张 dist 数组dist[v] 表示从 s 到 v 的最短路径长度。如果 s 到不了 vdist[v] 保持一个大数 INF。算法核心维护两个集合已经确定最短路的点集 S和还没确定的点集 T。1.2 贪心策略与松弛操作为什么一轮就能确定一个点整个算法只有两步核心动作选点和松弛。在 T 集合中找到 dist 值最小的点 u把它移入 S 集合。遍历 u 的所有出边 (u, v, w)尝试用 dist[u] w 去更新 dist[v]这个动作叫松弛。为什么第一步敢直接认定 dist[u] 已经是最短的因为所有边权都非负。假设存在一条从 s 到 u 的更短路径这条路径离开 S 集合时必然经过某个仍在 T 集合中的中间点 x。可是 dist[x] 不可能比 dist[u] 小吗不一定但这条更短路径的长度至少是 dist[x]到 x 的距离加上非负的剩余路程而 dist[x] ≥ dist[u]因为 u 是 T 中 dist 最小的点。所以任何经 x 绕行的路径都不可能比当前 dist[u] 更短。这就是贪心正确性的根基。用排队打饭类比窗口按号叫人已经叫到号的每一个人都保证是当前所有没取餐的人里排号最小的在没有任何人“插队到负号”的前提下叫到谁谁就真的是当前该取餐的。负权边就是“插队到更小号”的坏人后面再来一个负号前面刚被叫走的人就白叫了。1.3 负权边会导致什么后果一个反例就够看一张三个点的图s 到 a 边权 2s 到 b 边权 3b 到 a 边权 -2。从 s 出发两个邻居里 a 的 dist 是 2b 是 3于是第一轮把 a 标记为确定dist[a]2。但实际上从 s 到 b 再到 a总长度是 3 (-2) 1比 2 还短。Dijkstra 却永远不会再回头更新 a。所以结论很明确遇到负权边老老实实换 Bellman-Ford 或 SPFA。你可以在做题前先读题判断也可以写代码时用一个hasNegativeEdge标记做防护避免模板被误用。2. 朴素版手写邻接矩阵 O(V²) 三轮循环2.1 建图约定与数组初始化朴素版最朴素的存图方式是邻接矩阵适合描述稠密图。开一个二维数组 g[n1][n1]g[u][v] 存边权不存在边的地方全填 INF对角线 g[i][i]0。这里需要特别提醒INF不要直接用INT_MAX原因后面专门讲。全局数组默认是 0所以必须在 main 里先memset(g, 0x3f, sizeof(g))把整个矩阵刷成 INF再手动把 g[i][i] 置 0。这一步漏掉后面全乱套。#include bits/stdc.h using namespace std; const int N 1005; const int INF 0x3f3f3f3f; int g[N][N]; int dist[N]; bool visited[N]; int n, m, s; void dijkstra(int start) { memset(dist, 0x3f, sizeof(dist)); dist[start] 0; for (int round 1; round n; round) { // 第一步从未访问的点里挑一个 dist 最小的 int u -1; for (int v 1; v n; v) { if (!visited[v] (u -1 || dist[v] dist[u])) { u v; } } // 剩下的点都不可达提前结束 if (u -1) break; // 第二步标记为已确定 visited[u] true; // 第三步松弛 u 的所有邻点 for (int v 1; v n; v) { if (g[u][v] ! INF) { dist[v] min(dist[v], dist[u] g[u][v]); } } } }2.2 三轮循环的时间复杂度怎么算round循环最多跑 n 次每次找最小点要扫描 n 个候选这部分 O(n²)。松弛阶段在邻接矩阵下也要扫描 n 个点自然也是 O(n²)。整体复杂度O(n²)。这里的 n 是点数不是边数。所以朴素版适合 n 在几千以内、且图比较稠密的场景比如 n2000、边数接近百万的完全图O(n²) 反而比堆优化更稳。朴素版说“三轮循环”是因为人肉看代码时最外层是确定点的轮次内层第一个循环找点内层第二个循环做松弛。三个循环嵌套逻辑非常直白调试也最省心。2.3 朴素版的价值不只是“能跑通”很多初学者会跳过朴素版直接背堆优化模板我建议别这样。朴素版把“选点 松弛”两个核心概念用最原始的方式展示出来后面所有优化都是围绕“如何更快地选点”展开的。你只有亲眼看着这个 min 循环重复了 n 遍才能真正理解堆优化到底在优化什么。另外朴素版实现也是验证堆优化模板正确性的标尺。小数据下两个版本对拍dist 数组完全一致模板才敢放心用。我写堆优化时几乎每次都要先跑一遍朴素版对拍。3. 堆优化原理把“找最小值”从穷举换成优先队列3.1 朴素版慢在哪个环节朴素版在稀疏图上最大的浪费就是每轮线性扫描找最小 dist。n 到 10^5 的量级O(n²) 完全不可接受。现实中大部分图是稀疏图边数 m 和点数 n 同数量级这时候目标是把复杂度压到 O((nm) log n)。观察每轮能优化的事情其实只有一件用优先队列维护 T 集合里的候选 dist 值。每次往队列里插入一个{dist[v], v}弹出的时候自动拿到最小的那个。二叉堆的 push 和 pop 都是 O(log n)整体代价立刻降下来。3.2 堆优化模板vector 邻接表版本#include bits/stdc.h using namespace std; const int N 200010; const int INF 0x3f3f3f3f; struct Edge { int to, w; }; vectorEdge g[N]; int dist[N]; bool visited[N]; void dijkstra(int start) { priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq; memset(dist, 0x3f, sizeof(dist)); dist[start] 0; pq.push({0, start}); while (!pq.empty()) { int u pq.top().second; pq.pop(); if (visited[u]) continue; visited[u] true; for (const auto e : g[u]) { int v e.to; int w e.w; if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } }注意几个细节priority_queue默认是大顶堆必须带上greaterpairint,int否则每次弹出的都是最大距离的节点。队列里塞的是{距离, 节点}因为 pair 先比较 first距离小的自然先出来。把顺序反写成{节点, 距离}是新手最常见的错。状态弹出后要检查是否过期。入堆时某个节点可能是用旧距离塞进去的后来它的 dist 被更新得更小旧条目就作废了。3.3 为什么“弹出时标记 visited”而不是“入堆时标记”这个问题几乎每次面试都会考也是很多 WA 的根源。错误写法是入堆时立刻visited[v] true会导致什么假设起点到 u 先算出距离 10入堆后来通过另一个中间点算出到 u 的距离 8也入堆。如果第一次入堆时就标记 visited等距离 8 的第二条被弹出发现 visited 已经是 true直接跳过u 的最短路就被永久锁死在 10错误。所以正确姿势是从堆里弹出并确认它是当前最小候选时才标记 visited。或者干脆不标记 visited改用if (d dist[u]) continue;判断效果等价。我习惯两个都写因为 visited 能在后面省去重复松弛代码也更好读。3.4 堆优化的复杂度为什么是 O((nm) log n)每个点至多被“真正处理”一次每轮处理它的所有出边。总松弛次数 ≤ 边数 m。每次松弛可能触发一次 push所以堆中累计的条目数不超过 m 条每次 push/pop 都是 O(log m)因为 m 一般不会大于 n²log m 和 log n 同数量级。整体就是 O((nm) log n)。在稀疏图上这比 O(n²) 快一个量级以上。4. 存图选型对照vector 邻接表与链式前向星的全代码实现4.1 vector 邻接表直观、好调、日常首选上面堆优化模板用的就是 vector 邻接表。每个点开一个 vector里面存{目标点, 边权}。加边就是g[u].push_back({v, w})。遍历某点的所有出边直接范围 for 扫就行。优点很突出代码短、调试友好、不容易数组越界而且 STL 的 vector 在大多数 OJ 环境下表现足够稳定。缺点主要是两点动态扩容可能造成不必要的复制开销内存不是完全紧凑的极端大图下 cache 命中率略差。缓解扩容问题的小技巧如果预先知道每个点的出度规模可以g[u].reserve(estDegree)如果图是稀疏且点很多的图vector 的参赛级常数问题通常也不至于被卡除非命题人专门搞了一个 10^6 级别边数的卡常题。示例加边int n, m, s; cin n m s; for (int i 1; i m; i) { int u, v, w; cin u v w; g[u].push_back({v, w}); // 无向图需要补一条反边 // g[v].push_back({u, w}); }4.2 链式前向星用静态数组模拟链表链式前向星本质是用三个数组模拟“每个点的出边链表”也叫静态邻接表。核心变量就这几个head[u]点 u 的第一条出边的编号to[i]第 i 条边的终点w[i]第 i 条边的权值next[i]下一条同起点边的编号cnt当前边的总数从 1 开始自增加边时新边插到链表的头部也就是让新边的 next 指向原来的 head[u]再更新 head[u] 指向新边编号。这个“头插法”是核心理解它就能看懂所有遍历。#include bits/stdc.h using namespace std; const int N 200010; const int M 400010; // 边数记得开两倍无向图要存反向边 const int INF 0x3f3f3f3f; struct Edge { int to, next, w; } e[M]; int head[N], cnt; int dist[N]; bool visited[N]; void add(int u, int v, int w) { e[cnt] {v, head[u], w}; head[u] cnt; } void dijkstra(int start) { priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq; memset(dist, 0x3f, sizeof(dist)); dist[start] 0; pq.push({0, start}); while (!pq.empty()) { int u pq.top().second; pq.pop(); if (visited[u]) continue; visited[u] true; for (int i head[u]; i ! -1; i e[i].next) { int v e[i].to; int w e[i].w; if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } } int main() { memset(head, -1, sizeof(head)); cnt 0; int n, m, s; cin n m s; for (int i 1; i m; i) { int u, v, w; cin u v w; add(u, v, w); // add(v, u, w); 无向图需要 } dijkstra(s); for (int i 1; i n; i) { cout dist[i] ; } return 0; }这里有三处高频错误点head必须初始化为 -1cnt从 0 开始add里是cnt无向图每条边要插两次所以边数组要开到两倍。4.3 三种方案怎么选看数据范围说话方案建图结构时间复杂度空间调试体验推荐场景朴素版 邻接矩阵g[u][v]O(n²)O(n²)最直观n ≤ 5000 且图较稠密堆优化 vector 邻接表vectorEdge[N]O((nm)log n)O(nm)好绝大多数题n、m 到 10^5~10^6堆优化 链式前向星head/to/next 数组O((nm)log n)O(nm)中等卡常题、内存敏感、需要极致速度我的习惯是默认用 vector 邻接表写堆优化只有在题目数据规模超大、或者明显感觉到评测环境对 STL 不友好时才换链式前向星。两种模板都要背熟因为比赛中临时切换会出错最好平时就备好各自的“肌肉记忆版”。5. 隐蔽的坑INF 选择、重边、路径还原与错误写法5.1 INF 为什么要选 0x3f3f3f3f很多模板里用0x3f3f3f3f因为它在十进制是约 10.6 亿比 int 最大值小一半左右。两个这样的 INF 相加约 2.1e9不会超过 int 上界因此dist[u] w计算时不会溢出成负数。如果用INT_MAX当 INFdist[u] w一旦执行就会溢出成负数dist 被更新成负数后续全乱。如果题目边长和距离都可能超过 int 范围那就干脆把所有距离相关变量换成long longINF 用4e18或LLONG_MAX / 4注意memset对 long long 数组并不适用老老实实写fill(dist, dist N, INF)。5.2 重边不用慌但要分清存图方式图里两个点之间可能出现多条边不同的存图方式处理方式不同vector 邻接表、链式前向星每条边都存下来Dijkstra 松弛时自然会把短的那条留下无需特判。邻接矩阵必须g[u][v] min(g[u][v], w)因为矩阵每个位置只能存一条边只存最短的即可。无向图一定要两条边都加。很多新手跑出了一个“很接近答案但有偏差”的结果多半就是漏掉了反向边。5.3 记录具体路径在松弛时保存前驱如果题目要求输出最短路径需要额外开一个pre[v]数组记录 v 的前驱节点。在松弛成功时更新pre[v] u。起点 s 的 pre 初始化为 -1。要还原从 s 到 t 的路径时从 t 出发沿着 pre 往前回溯一路塞进 vector最后反转即可vectorint path; for (int cur t; cur ! -1; cur pre[cur]) { path.push_back(cur); } reverse(path.begin(), path.end());注意链条长度极限下不会有环因为每条边权非负pre 只会指向真实更短的路径。如果图里有 0 权环理论上可能出现多个等价前驱但只要记录任意一个得到的仍是合法最短路。5.4 自环怎么处理自环就是 u 到 u 的边。因为边权非负dist[u] w dist[u]松弛不会触发更新所以自环完全不影响结果留着即可。5.5 “入堆时才标记 visited” 的典型错误复盘把错误版完整写出来方便对照// 错误示例 if (dist[u] w dist[v]) { dist[v] dist[u] w; visited[v] true; // 错v 可能还会被更短距离更新 pq.push({dist[v], v}); }第一次更新时给 v 标记已访问等后续更短路径出现v 的更大距离已经从堆里弹出但因为 visited 为 true 被丢弃结果错误。如果你调试时发现“答案比标准答案大一点”优先检查 visited 是不是提前标记了。5.6 一个判断这题到底能不能用迪杰斯特拉做题前先做三道自检边权有没有负数有立刻换 Bellman-Ford / SPFA。点数是否超过 10^5是直接上堆优化不要写朴素版。是否要求“经过不超过 k 条边”的最短路是Dijkstra 管不了维度约束这要上带层次的 DP 或 Bellman-Ford 思路。这三条先想清楚再动手能少交很多次 WA。6. 适用边界与进阶技巧虚拟源点、反向建图与我的经验清单6.1 多源问题超级源点一劳永逸有时候起点不是一个而是多个。比如有 k 个仓库要算离某个居民点最近的仓库距离。一个自然的做法是每个仓库都跑一次 Dijkstra复杂度乘上 k非常浪费。标准技巧是新建一个超级源点 S从 S 向每个仓库连一条 0 权边然后从 S 跑一次 Dijkstra。这样所有合法路径都必须经过某个仓库等价于从最近的仓库出发。注意这个超级源点只入不出别给它加回流边否则会产生绕回源点的假路径。6.2 反向建图所有点到点 T 的最短路如果你只需要从某个固定终点 T反向计算“所有点到 T 的距离”不需要对每个点都跑一次。把图的每条边反向即原来 (u, v, w) 变成 (v, u, w)再从这个 T 出发跑一次 Dijkstra。由于原图中从 x 到 T 的任意路径在反向后都会变成一条从 T 出发到达 x 的路径且路径总长不变所以反向后的 dist[x] 恰好就是原图 x 到 T 的最短路。实战里这个技巧经常和“多点查询最近出口”“多区域到中心机房延迟”这类问题绑定熟练使用能少写 k 次 Dijkstra。6.3 我的经验清单写每一道最短路题前都过一遍写多了之后我总结了一套固定检查项分享出来应该能帮你省很多调试时间数组越界n 是点数边数 m 可能很大。链式前向星边数组开2 * 最大边数vector 邻接表不用开边数但要注意节点编号从 1 还是 0 开始。类型选择所有 dist、边权、加法都可能超过 int最稳妥的方式是统一用long long只在确认数据范围时才用 int。初始化完整memset(head, -1, sizeof(head))、memset(dist, 0x3f, sizeof(dist))、visited全部 false一个都不能少。无向图补边加完 (u,v) 别忘 (v,u)这是 WA 率最高的低级错误。输出格式dist 不可达时输出什么很多题要求输出-1而不是 INF读题时先确认。调试顺序先跑小规模样例打印弹出的(d, u)和每次更新后的 dist如果和朴素版对拍不一致第一眼看松弛条件和 visited 的标记时机。别硬套模板如果题目是求最大概率路径、最大带宽路径把“松弛”里的小于号改成大于号松弛加法换乘法。Dijkstra 的核心思想可以泛化到很多“非负代价”的最优化问题要学会改而不是只会抄。最后再分享一个实用小建议平时练习时三种版本都要写一遍不要只背一个堆优化模板。朴素版帮你建立算法直觉vector 邻接表帮你快速出题链式前向星帮你应付极限数据。真到比赛或者面试手写代码时你脑子里要有三个预案根据数据范围现场选型而不是被一个模板绑死。这套东西我用了很久至今仍是每次写图论题的固定流程。