前阵子训练营有个同学跟我吐槽说一看到图论两个字就头皮发麻觉得那是ACM选手的专利。结果真跟着代码随想录走到day52把图论专题5刷下来他自己都没想到能被最短路问题虐得这么心甘情愿。今天这篇就想聊聊我在这个专题里的核心收获包括建图选型、四种最短路算法的拆解、从题意到AC的完整链路还有那些不写在模板注释里的坑。适合正在刷图论、准备面试或者被最短路径绕晕的朋友老手也可以直接跳到后面看问题排查部分应该能帮你少走几步弯路。1. 图论专题5到底在练什么先看懂这一部分的定位1.1 一整条图论主线是怎么走到这里的代码随想录的图论安排是有梯度的不是上来就让你背Dijkstra模板。专题前面先解决的是图怎么存、怎么遍历从邻接矩阵、邻接表到DFS和BFS把最基础的东西夯实。后面又花时间讲了并查集和最小生成树到专题5的时候整个训练营已经把静态的图吃得差不多了剩下的就是最短路问题——也就是动态求两点之间的最优路径。到了day52这个节点一个很现实的信号是图论的基础模型你都已经见过了卡哥的题单也刷到比较深的位置。这时候如果还不会建图、不会选算法前面那些题等于白练。所以专题5的设计心思很明确就是逼你把图论抽象能力和算法选型能力合二为一。说白了前面是认识零件这讲是组装整车。最短路问题在面试里的出现频率有多高字节、阿里、腾讯这些大厂主管面经常拿一个带权图的题出来不看你会不会背代码而是看你能不能把业务场景翻译成图然后告诉面试官这里该用Dijkstra因为我们没有负权边。1.2 最短路问题的核心模型与思考框架最短路问题的标准模型是给定一个有向图偶尔无向每条边上有权重求某个源点到其他所有点单源最短路或者任意两点之间全源最短路的最小权重和路径。我建议大家先形成一个思考框架拿到题先问三个问题——边的权重有没有负数是单源查询还是多源全查图的规模有多大这三个问题的答案几乎可以直接决定你要用哪种算法。负权边直接排除Dijkstra全源优先考虑Floyd图特别大就要避开O(V^3)的Floyd。这个框架建立起来之后图论专题5的题就不再是背四种算法模板而是变成一个条件匹配的过程。图论最短路这类题还有一个容易忽略的点图不一定是为了最短路出现的。很多题目表面是二维网格、是迷宫、是换乘线路剥开之后全是图模型。所以专题5真正的核心能力不是记代码而是看穿伪装的能力。2. 建图选型所有图论题的第一步都是这步很多同学学最短路的时候有个通病上来就背Dijkstra的二维数组写法完全不知道代码里那个vectorpairint, int是从哪来的。这里得先停下来好好讲讲建图因为后面所有算法都是在图已经建好这个前提下跑的。2.1 邻接矩阵写起来爽跑起来哭邻接矩阵用一个二维数组来存边代码最简单判断两个点之间有没有边、边的权重是多少都是O(1)时间。我最早学图论的时候特别喜欢用这个方式因为初始化一个N*N的二维数组把每条边填进去就完事了。可一旦图规模上来邻接矩阵就变成了灾难。空间复杂度是O(V^2)注意这里的V是点的数量。如果题目给了10万个点你开一个10万乘10万的数组至少是40G内存直接爆掉。实际竞赛和面试题里超过1000个点用邻接矩阵就已经很勉强了。而且遍历某个点的所有邻居需要O(V)也就是说哪怕这个点只有1条边你也要扫一遍整个数组。所以我现在对邻接矩阵的态度是只用来解面试场景下明确告诉这是一张稠密图的题或者数组规模特别小比如小于200个点的题。其余情况一律看邻接表和链式前向星。2.2 邻接表工程实践的正确姿势邻接表的核心思路是只为每个点维护自己的邻居列表谁有边就存谁的没有边就空着。这样存图的总空间是O(VE)E是边数。对于稀疏图来说这个存储量比邻接矩阵小好几个数量级。在C里我常用vectorvectorpairint, int内层pair的第一个数是终点节点第二个数是权重。比如graph[u].push_back({v, w})就是把一条从u到v、权重为w的边加入图。在Python里则用字典或者列表套列表graph[u].append((v, w))就行。邻接表另一个好处是遍历一个点的所有邻居特别自然一个for循环拿到所有pair直接读终点和权重。写Dijkstra、SPFA、拓扑排序的时候手感特别顺。用邻接矩阵写这些算法每次遍历都要嵌套一层全量循环既难看又容易超时。从我刷题经验来看90%以上的最短路题用邻接表就够了没必要再折腾更底层的存法。2.3 链式前向星竞赛玩家才懂的浪漫链式前向星是C竞赛圈很常用的一种静态数组存图方法本质是用三个数组head、to、next来模拟链表把所有边串起来。它比vectorvector 性能更好因为vector在插入过程中会扩容产生额外的动态分配开销。链式前向星所有空间一次开好每个节点的邻居通过head[u]找第一条边然后沿着next数组一条条摸下去。有同学可能会问面试题有必要用链式前向星吗说实话绝大多数没必要面试官更看重你的思路和代码可读性vector版邻接表完全够了。但如果目标是打ACM、ICPC这种比赛链式前向星必须会因为比赛数据有时候会到百万级的边vector扩容那点性能差距真的会影响能否卡过时限。我自己的习惯是日常训练和面试准备用邻接表打周赛如果发现内存卡得死就用链式前向星。专题5的题练下来你会发现大部分题邻接表都能过链式前向星更多是手速和习惯问题。3. 四种最短路算法逐个拆解原理、代码与选中逻辑最短路算法里大家接触最多的就是Dijkstra但面试和竞赛往往会用Bellman-Ford、SPFA和Floyd来设坑。这里我按算法原理-适用条件-代码注意事项的结构分别拆一下。3.1 Dijkstra贪心思想为什么在这里就对了Dijkstra解决的是单源最短路问题要求图的边权重都是非负数。核心思路是贪心维护一个已经确认最短路的集合每次从还没确认的节点里挑一个距离源点最近的点把它加入集合然后用它去松弛更新它所有邻居的距离。听着有点像BFS但BFS只适用于无权图Dijkstra通过优先级队列Priority Queue保证每次弹出的都是当前全局距离最小的点这也是它能在O((VE)logV)时间内跑完的关键。优先队列里同时存当前距离和节点编号每次弹出来之后要先判断这个pair是不是过期数据。判断过期数据这个点我踩过坑。因为同一个节点可能被多次加入优先队列比如第一次距离是5后来被更新成3队列里就会出现两个记录。处理方式是在弹出后检查一下if (dist[node] currentDist) continue;如果dist数组里记录的距离已经比这个pair里的距离小说明这是老数据直接跳过。不写这个判断性能会退化甚至可能因为重复松弛导致逻辑错误。Dijkstra模板代码基本长这样C邻接表版#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; void dijkstra(int s, vectorvectorpairint, int graph, vectorint dist) { int n graph.size(); dist.assign(n, INF); 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 (dist[u] d) continue; // 跳过过期记录 for (auto [v, w] : graph[u]) { if (dist[v] d w) { dist[v] d w; pq.push({dist[v], v}); } } } }这里INF我习惯用0x3f3f3f3f而不是INT_MAX。因为INT_MAX加上一个正数会溢出变成负数导致松弛判断完全错乱。0x3f3f3f3f是十进制约10亿级别足够大而且两个0x3f3f3f3f相加不会溢出int范围是一个在竞赛和面试里都很安全的伪无穷大。3.2 Bellman-Ford负权边的老实人解法Dijkstra处理不了负权边的原因其实很有意思。因为贪心一旦确认某个点距离最小就把这个点定下来了以后不再更新。如果存在负权边后面出现的更短路径完全可能绕到已经确认的点所以贪心的前提就崩了。Bellman-Ford用一个很老实的策略没有确认这个操作做V-1轮全量松弛。每一轮都遍历所有边尝试用边的起点更新终点。为什么要做V-1轮因为在一个没有负环的图里从源点到任意点的最短路径最多包含V-1条边所以V-1轮松弛之后所有距离必然达到稳定状态。Bellman-Ford的代码实现比Dijkstra还简单三重循环改成两重就行void bellmanFord(int s, int n, vectorEdge edges, vectorint dist) { dist.assign(n, INF); dist[s] 0; for (int i 0; i n - 1; i) { for (auto e : edges) { if (dist[e.from] ! INF dist[e.from] e.w dist[e.to]) { dist[e.to] dist[e.from] e.w; } } } // 第V轮再松弛如果还能更新说明存在负环 for (auto e : edges) { if (dist[e.from] ! INF dist[e.from] e.w dist[e.to]) { // 图中有负环无法求出稳定最短路 } } }注意第二段循环这个就是负环检测。如果第V轮还能更新说明图中存在一条负权回路最短路径可以被不断缩减到负无穷。面试问Bellman-Ford的时候十次里有八次要问负环检测这个判断一定要能现场手写出来。3.3 SPFA队列优化与它的爱恨情仇SPFAShortest Path Faster Algorithm本质上是对Bellman-Ford的优化。Bellman-Ford每一轮都遍历所有边但很多时候很多边根本不会引起松弛。SPFA的做法是只把成功更新了邻居的节点加入队列下一轮只从队列里取这些可能引起连锁反应的节点来处理。SPFA的平均时间复杂度确实比Bellman-Ford好很多稀疏图上接近O(E)最坏情况下则退化到O(VE)。我对SPFA的使用建议是能用Dijkstra优先用DijkstraSPFA只有在图里明确有负权边且没有负环时才考虑。还有一个点如果面试官问SPFA会死循环吗不是说代码写错而是如果图里有负环SPFA会因为距离不断变小而无限循环下去。所以SPFA也需要一个数组记录每个节点入队的次数如果某个节点入队超过V次就说明有负环。SPFA核心代码片段void spfa(int s, vectorvectorpairint, int graph, vectorint dist) { int n graph.size(); dist.assign(n, INF); vectorint cnt(n, 0); vectorbool inQueue(n, false); queueint q; dist[s] 0; q.push(s); inQueue[s] true; while (!q.empty()) { int u q.front(); q.pop(); inQueue[u] false; for (auto [v, w] : graph[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; if (!inQueue[v]) { q.push(v); inQueue[v] true; if (cnt[v] n) { // 存在负环 return; } } } } } }这里的inQueue数组很重要它避免同一个节点同时出现在队列里多次减少无效计算。cnt数组就是入队次数计数超过n直接认为有负环避免死循环。3.4 Floyd最简单的全源最短路Floyd算法解决的是全源最短路询问任意两点之间最短距离。它的思路可以用一句话概括用每个节点当中转站尝试把任意两点之间原有的路径变得更短。写成三重循环就是for k in 0..n: for i in 0..n: for j in 0..n: dist[i][j] min(dist[i][j], dist[i][k] dist[k][j])。这个算法的时间复杂度是O(V^3)空间复杂度O(V^2)。所以Floyd只适合点数量很小的场景一般V在500以内可以考虑再多就等着超时或者爆内存。Floyd实现起来非常朴素不需要建邻接表直接维护一个二维距离矩阵就行。初始化时把每对点的距离置为INF自己到自己置为0有边就填权重然后三重循环更新。它还有一个隐藏功能可以在不额外写很多代码的情况下通过更新过程顺带求出路径的前驱节点方便恢复完整路径。我用Floyd的场景不多主要是一个图上反复询问任意点对最短路且点数量少时才用。比如一些面试题给一个最多20个节点的图问任意点对最短路Floyd写起来比跑V次Dijkstra简单太多。4. 实际操作一道经典题从题意到AC的完整链路光讲理论不够这里我用一道在代码随想录图论专题里非常经典的问题来串一遍完整流程求有向无环图中从一个源点出发到其余所有点的最短路径这里还没引入负权或环的复杂性后面再扩展。4.1 题目建模把文字翻译成图题目一般不会直接告诉你这是一张图而是给你一段描述比如给定n个城市m条航班线路每条线路有飞行费用求从城市A到城市B的最少费用。拿到这样的题目第一步就是建模。我建模的一般步骤是把城市抽象成节点把航班线路抽象成带权有向边把飞行费用抽象成边的权重把最少费用翻译成求最短路。这一段听起来很简单但很多同学就是栽在这里因为题目可能会嵌套在其他语言外壳里比如某公司有n种操作系统升级过程有依赖关系每次升级消耗一定量子求最小升级消耗。不管壳怎么变内部都是同一个图模型。如果题目要求的是从一个城市到另一个城市那就是单源单目标的最短路Dijkstra跑完直接看dist[target]即可。如果题目说要求从起点到所有城市仍然是用单源最短路算法dist数组就是答案。4.2 参数选择为什么这张图要用Dijkstra建模完成之后我通常会列一个参数表快速判断算法判断条件选择结果边权全部非负单源最短路Dijkstra优先队列优化存在负权边单源最短路Bellman-Ford或SPFA存在负环问任意最短路不存在最短路直接报告有负环询问全源最短路图较小Floyd边权全部为正的稠密图朴素Dijkstra O(V^2) 也可以上面这道题里航班费用必然是正数没有负权边单源查询所以Dijkstra是正确且效率最高的选择。时间复杂度O((VE)logV)完全够用。另外补充一个细节如果题目是无向图Dijkstra同样可以用把一条无向边当成两条有向边分别插入两个节点的邻接表即可这属于建图时的基本操作。4.3 代码复现与调试实录我在调试这道题的时候遇到过一个问题很典型我把所有节点的dist初始值都设成了INF但忘记设置dist[source] 0。当时的表现是所有输出都是INF完全没有距离被更新。排查方式很简单先在入口处打印一下dist数组的初始值马上就能看出来。还有一次我没有在优先队列弹出节点时跳过过期记录导致同一个节点被反复松弛。结果在小数据样例上侥幸通过了但换到大数据样例直接超时。后来养成一个习惯写完Dijkstra先随手在一个有数十个节点的随机图上跑一遍用暴力BFS对比结果确保正确性。刷题阶段我建议你准备一个模板文件把上面提到的Dijkstra、Bellman-Ford、SPFA、Floyd都提前写好带注释然后在每一道新题上套模板。这不叫偷懒相反这是竞赛选手最常用的策略算法模板固定化把注意力放在建图和题意转化上因为那才是题目的真正难点。5. 顺带把最小生成树和并查集也串起来代码随想录图论专题5之前训练营里已经出现过并查集和最小生成树的内容。为什么会放在前面因为图论是一个大体系最短路并不是唯一求最优的问题。很多同学学到后面容易把最短路和最小生成树搞混这里专门辨析一下。5.1 Kruskal与Prim最短路容易和谁搞混最小生成树的目标是在无向连通图中找到一棵包含所有节点的树使得树的所有边权重之和最小。说白了是找一个连接所有点且总代价最小的结构而不是从某个点出发到另一个点的最短路径。Kruskal算法的思路是贪心把所有边按权重从小到大排序用并查集维护节点是否已经连通每次选一条不会形成环的边加入生成树直到所有点连通。Prim则是从一个起点出发不断把距离已选集合最近的节点拉进来。这里把Dijkstra和Prim摆在一起看很有意思两者代码结构看起来几乎一样都是维护一个到集合的距离并用优先队列选最优但Dijkstra比较的是到源点的累计距离Prim比较的是到已选集合的直接边距离。面试官特别喜欢拿这个暗坑来考察你是真懂还是只背模板。5.2 并查集实现细节路径压缩与按秩合并并查集不是一个具体的图算法而是图论里高频使用的数据结构。在Kruskal里它用来判断两个点是否已经在同一个集合也就是判断加一条边会不会构成环。核心操作就两个Find找根节点Union合并两个集合。基础实现不到十行但要写对优化。路径压缩就是把find过程中遇到的所有节点都直接挂到根节点下这样后续查询几乎是O(1)。按秩合并则是让树尽量矮让小树合并到大树上减少find的深度。两个优化加在一起均摊复杂度可以认为是阿克曼函数的反函数几乎常数时间。写并查集最容易犯的错误是union的时候忘记先find。如果直接把一个节点的父指针挂到另一个节点上很可能把非根节点当作根来连接导致环的出现或者集合分裂。我建议所有union操作都这样写rootX find(x); rootY find(y); if (rootX ! rootY) parent[rootX] rootY;先统一拿根再连接不然排查起来非常痛苦。5.3 从最短路到最小生成树两种最的辨析最短路关心的是两点之间最小生成树关心的是全图连通。举个例子一个城市有A、B、C三个区最短路可以回答从A到C最快怎么走最小生成树回答的是要让三个区互相连通修路最少要花多少钱。所以我做题时有个习惯先看问题问的是从一个点到另一个点的距离还是让所有点连通的最小总代价。前者往最短路靠后者往最小生成树靠。这个判断失误比算法写不出来还要致命。代码随想录把并查集和最小生成树放在最短路前面就是希望你先建立图结构和连通性的直觉再去做路径优化。到了专题5你在脑子里已经有了一张完整的图论网络图知道哪个知识挂在哪个节点下面这对接下来的刷题帮助特别大。6. 常见问题与排查技巧实录图论专题5练到后半段大家的代码都写得越来越快但报错和超时的花样也越来越多。这里把我自己踩过和帮别人排查过的几个经典问题整理成速查表基本都是高频坑。6.1 死循环、超时、越界的经典死法死循环最常见的原因是SPFA遇到负环我之前已经说过解决办法是记录入队次数超过V次直接退出。另一个死循环容易出现在BFS遍历图的时候——如果没有visited数组一个无向图中两个节点之间会来回走永远停不下来。BFS遍历图时必须每次入队就标记visited而不是等到出队才标记否则会出现重复入队导致队列无限增长。超时问题先别急着优化算法先检查是不是邻接表写成了O(V)遍历。有些同学明明用的是邻接矩阵却在外层套了两三层循环一个上千个点的图直接就卡死了。改用邻接表之后同样的逻辑可能快上百倍。如果确实需要更极致性能再考虑链式前向星。越界问题则主要集中在数组下标上。图的节点编号如果是1到n你在初始化vector的大小时写成n而不是n1一跑就段错误或者读到非法内存。我自己一般统一用0-index或者1-index然后所有循环都跟它对齐写完之后数一遍vector大小、for循环边界、输入读取方式是否完全一致。这个习惯帮我少了很多半夜debug。下面这张速查表建议存一下症状可能原因排查方法输出全是INF没设dist[s]0图不连通打印dist初始化检查起点编号超时邻接矩阵用在稀疏图换成邻接表检查是否反复松弛过期节点死循环负环BFS没标记visited打印入队次数检查visited标记时机段错误数组开太小编号从1开始但开了n统一索引规范打印下标结果偏大没更新最短距离或更新逻辑写反手跑小数据逐行打印每组松弛6.2 为什么Dijkstra在负权图上翻车面试爱问的一个经典问题也是训练营里讨论最多的Dijkstra遇到负权边为什么会错我用自己的话讲清楚Dijkstra每次从优先队列里弹出的点是当前已知距离最小的点它假设这个距离之后不会再变小。这个假设只在所有边权非负时成立因为一个正权边不可能让某个点绕一圈后距离变得更小。但图里有负权边的时候完全可能出现一条藏着的更短路径。举个例子源点s到a的距离是5s到b的距离是3b到a有一条-4的边。Dijkstra在第一轮就会选b作为确认节点但真正到a的最短路径是s→b→a总距离是-1比直接s→a的5小太多。可惜的是当Dijkstra确认b之后它可能早就把a的距离设为5并且以为那就是答案了不会再去翻旧账。这就是贪心提前确认带来的漏洞。理解这个原理之后你就明白Bellman-Ford为什么要做V-1轮松弛——它不提前确认任何点每一轮都可能推翻之前的结论。SPFA则是在Bellman-Ford基础上只对被影响的节点做后续更新同时仍然不预设任何已确认点。6.3 建模能力的训练方法有同学觉得题意转成图这个能力很玄学其实它是可以刻意训练的。我自己的方法很简单每次刷题之前不管题目本身是不是图论题都先在草稿纸上用笔画出节点代表什么、边代表什么、权重代表什么这三个问题的答案。如果画图的时候能5分钟内明确回答就说明建模没跑偏。练到中后期我会专门挑一些不是图论标签的题目来反向练习。比如字符串转换、依赖调度、状态压缩类题目看看它们能不能被抽象成最短路问题。比较典型的是单词接龙——单词是节点单词间如果能转换就加一条权重为1的边最短转换次数就是最短路长度。这种跨领域训练才是图论专题5真正想带给你的能力。另外我还习惯把同种建模模板归类网格图就直接把每个格子当成一个点相邻格子之间连边有向依赖图就注意处理环拓扑排序与最短路结合时要小心按照拓扑序来松弛。这些模板归纳多了到考场上自然一眼就能看穿题目的本质。写到最后分享一个我自己的小习惯从day52开始我不再追求每道题AC之后立刻开下一题而是花几分钟做个复盘把题目的建模方式、陷阱、算法选择理由写进一个专门的本子。这样回头看时图论专题5的题目能形成一张自己的知识地图而不是零散的一百多道题名。下次某个朋友再跟我吐槽图论好难我就直接告诉他难的不是算法是建模和选型的直觉这两个东西靠刷题量堆出来但更靠每次刷完题多问自己一句为什么。