学过图论的人都会遇到这么一道入门题信息学奥赛一本通上的P1381“城市路”。题面很朴素给你n个城市和m条道路问从1号城市到n号城市的最短路径长度。很多人觉得它简单只写一个朴素Dijkstra就过了然后就把这道题扔了。实际上这一题特别适合用来把四种最短路写法一次练熟——朴素Dijkstra、堆优化Dijkstra、Bellman-Ford、SPFA。我给学生讲这题的时候会故意让他们用四种写法各交一遍收获比刷十道同类题还大。下面我把四种做法的思路、代码和踩过的坑一起说一说。1. 题目原型与四种做法怎么选1.1 题面到底在问什么先别急着写代码花两分钟把题看透。P1381说的是有n个城市编号从1到n城市之间有m条路路是无向的所以从a能到b从b也能到a每条路有一个长度。要求输出从城市1到城市n的最短距离。如果1到n不连通输出-1。这个题面里没有说路是单向的所以建图时要加两条边。很多新手第一次就挂在无向图上只加了一条边结果只有一半样例能过。另外注意可能有多条路连接同一对城市这时候要取最短的那条。重边看似麻烦其实在松弛时自然会被处理因为你拿着较短的距离去更新较长的根本不会成为答案。还有一个经常被忽略的边界当n1时城市1就是城市n最短距离应该是0。可别程序一跑发现dis[1]还是INF就输出-1那就错了。1.2 为什么拿这道题练四种做法既然是最短路为什么我不直接讲Dijkstra而是说四种做法因为最短路模板题的意义不是让你背一个模板而是让你理解不同算法的适用边界。朴素Dijkstra能在稠密图上发挥优势因为它的时间复杂度O(n^2)不依赖边数图的规模再密都扛得住。堆优化Dijkstra在稀疏图上几乎无敌复杂度O(m log n)m是边数n是点数边少了自然快。Bellman-Ford能处理负权边虽然慢但是思路简单还能用来检测负环。SPFA是Bellman-Ford的队列优化版在随机图上的平均表现不错但最坏情况能把你卡哭。把这四种都写一遍才算真正把图论最短路的基础打牢。我上课时的比喻是朴素Dijkstra是步行堆优化Dijkstra是骑车Bellman-Ford是手动挡汽车SPFA是自动挡汽车。你当然可以只开自动挡但万一哪天车子给你换挡的权利你却不知道变速器怎么工作那就尴尬了。另外提到Floyd的同学要注意Floyd是任意两点之间的最短路复杂度O(n^3)这种单源问题拿它做不是不行是浪费。所以这里不把Floyd算进四种做法。2. 朴素Dijkstra邻接矩阵是基础2.1 核心思想与代码实现Dijkstra的核心是贪心从起点出发每次找到一个“当前距离最短且还没有确定最终答案”的城市它就是这一轮确定下来的点。然后从这个点出发尝试刷新其它城市的距离。因为每条边都是非负的已经确定最短路的点不会再有更短的路径所以这个贪心是对的。如果你没写过建议先画一个只有4个城市的小图手跑一遍。比如1号到2号距离12号到4号距离31号到3号距离43号到4号距离1。第一步确定1号刷新2号和3号第二步选中2号刷新4号为4第三步选中3号刷新4号为2等等1-343-41所以4的路径是5。其实2号到4是31-2-4总长41-3-4总长5。所以确定顺序应该是1,2,4,3。这个过程多跑几遍比死记代码强。下面是一份邻接矩阵实现的朴素Dijkstra#include bits/stdc.h using namespace std; const int N 205; const int INF 0x3f3f3f3f; int n, m; int g[N][N]; int dis[N]; bool vis[N]; void dijkstra() { memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis)); dis[1] 0; for (int i 1; i n; i) { int u -1; int minv INF; for (int j 1; j n; j) { if (!vis[j] dis[j] minv) { u j; minv dis[j]; } } if (u -1) break; vis[u] true; for (int v 1; v n; v) { if (!vis[v] g[u][v] ! INF) { if (dis[u] g[u][v] dis[v]) { dis[v] dis[u] g[u][v]; } } } } } int main() { cin n m; memset(g, 0x3f, sizeof(g)); for (int i 1; i m; i) { int a, b, w; cin a b w; g[a][b] min(g[a][b], w); g[b][a] min(g[b][a], w); } dijkstra(); if (dis[n] INF) cout -1 endl; else cout dis[n] endl; return 0; }这里用0x3f3f3f3f做INF是因为int是4字节memset按字节填充后每个字节都是0x3f整个整数就是0x3f3f3f3f约等于10^9。两个INF相加也不会溢出int方便在松弛时做加法比较。2.2 复杂度分析与适用场景朴素Dijkstra的时间复杂度是O(n^2)。外层循环确定n个点内层找最小值扫描一次再扫描所有点做松弛所以两重循环常数很小。空间上需要开一个n×n的邻接矩阵如果n比较大比如10^5矩阵根本开不下所以它只适合n比较小的稠密图。什么是稠密图就是边数m接近n^2的图。比如n1000m100000甚至m500000邻接矩阵虽然还能开下但用堆优化会觉得大材小用。反过来n100000m200000这时候邻接矩阵开不了而且O(n^2)稳超时必须换堆优化。在一本通这道题上数据范围给得比较温和朴素写法能过。但你要知道它能过不是因为最优而是因为题目放水。我读题第一步一定先看n和m如果n超过1万我绝对不会写这个写法。3. 堆优化Dijkstra稀疏图的默认解3.1 用优先队列替代线性扫描朴素Dijkstra慢在哪里慢在每次都要在dis数组里扫一遍找最小值这个操作是O(n)的。改进的思路很简单用一个优先队列维护当前所有“可能成为下一个确定点”的城市堆顶就是距离最小的那个。每次弹出堆顶如果它已经过时就跳过否则确定它并用它更新邻接点更新成功后把新的状态丢进堆里。这样取最小值的代价从O(n)降到O(log n)整体复杂度变成O(m log n)。这里的m是松弛操作的次数实际是边数的常数倍。代码#include bits/stdc.h using namespace std; const int N 100005; const int INF 0x3f3f3f3f; struct Edge { int v, w; }; int n, m; vectorEdge adj[N]; int dis[N]; void dijkstra() { memset(dis, 0x3f, sizeof(dis)); dis[1] 0; priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq; pq.push({0, 1}); while (!pq.empty()) { int d pq.top().first; int u pq.top().second; pq.pop(); if (d ! dis[u]) continue; for (int i 0; i (int)adj[u].size(); i) { int v adj[u][i].v; int w adj[u][i].w; if (dis[u] w dis[v]) { dis[v] dis[u] w; pq.push({dis[v], v}); } } } } int main() { cin n m; for (int i 1; i m; i) { int a, b, w; cin a b w; adj[a].push_back({b, w}); adj[b].push_back({a, w}); } dijkstra(); if (dis[n] INF) cout -1 endl; else cout dis[n] endl; return 0; }这里最关键的一行就是priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq;。因为优先队列默认是最大堆而我们需要最小堆所以要加greaterpairint,int。很多人第一次写就忘掉导致每次弹出来的是距离最大的点跑出来的答案完全是错的。3.2 细节重边、自环、判重堆优化Dijkstra最大的坑是“旧状态”的处理。一个点可能在松弛过程中被更新多次每次更新都会向堆里丢一个pair。比如1号点从距离0更新到0之后又可能被某个更短路径再次更新注意Dijkstra中一个点一旦被确定距离不会更小。但在它确定之前可能先进堆多次。比如起点1先通过2号更新到3号距离10后来又通过4号更新到3号距离5那么堆里就有(10,3)和(5,3)。如果不在弹出时判断if (d ! dis[u]) continue;那么(10,3)被弹出时会当作有效状态再处理一遍虽然最终答案可能还是对的但多做了很多无用功甚至可能因为处理顺序导致复杂度退化。重边在这种情况下不需要特别处理。因为松弛时只有更小的距离才会更新所以较长的重边天然会被忽略。自环也是正权自环不会让距离变小负权自环那属于贝尔曼家族的领域了。另外无向图建边一定要双向。我见过一个学生用堆优化做这题只加了adj[a].push_back({b,w})忘了加反向边。结果样例能过因为样例可能刚好只需要从1到n沿一个方向走但测试数据里一旦需要走回头路直接WA。4. Bellman-Ford带负权的“笨办法”4.1 松弛n-1轮的原因Dijkstra不能处理负权边这是它的死穴。为什么因为已经确定最短路的点可能因为一条负边被改变。比如起点到A距离5到B距离3但B到A有一条-4的边那A的最短路其实是-1。Dijkstra第一次确定B第二次确定A这个例子不会错但构造更复杂的例子就能让它错。所以遇到负权边需要换思路。Bellman-Ford的做法特别直白对所有边做“松弛”一共做n-1轮。每一轮里对于每条边(u,v)尝试用dis[u] w去更新dis[v]对于无向图还要用反方向再更新一次。为什么是n-1轮因为一条最短路径上最多只能有n-1条边如果路径上有n条边那必然有重复点去掉环之后路径只会更短。所以每轮松弛至少能把一条边对应的距离固定下来n-1轮足够找到所有最短路。代码如下#include bits/stdc.h using namespace std; const int N 100005; const int M 100005; const int INF 0x3f3f3f3f; struct Edge { int a, b, w; }; int n, m; Edge e[M]; int dis[N]; void bellman_ford() { memset(dis, 0x3f, sizeof(dis)); dis[1] 0; for (int i 1; i n; i) { bool flag false; for (int j 1; j m; j) { if (dis[e[j].a] e[j].w dis[e[j].b]) { dis[e[j].b] dis[e[j].a] e[j].w; flag true; } if (dis[e[j].b] e[j].w dis[e[j].a]) { dis[e[j].a] dis[e[j].b] e[j].w; flag true; } } if (!flag) break; } } int main() { cin n m; for (int i 1; i m; i) { cin e[i].a e[i].b e[i].w; } bellman_ford(); if (dis[n] INF) cout -1 endl; else cout dis[n] endl; return 0; }这个代码和Dijkstra比最大的优势是思路简单不需要优先队列也不需要判断是否访问过。代价是慢O(nm)。如果n是1000m是10000那要跑一千万次勉强能接受但如果n是100000m是200000直接超时到天荒地老。4.2 如何用它判负环本题不适用但是扩展Bellman-Ford还有一个附带技能判断图中是否存在负权环。方法是在n-1轮松弛结束后再对所有边做一轮松弛。如果这一轮还能成功更新某个dis就说明存在负环。原因还是“最短路最长n-1条边”这个性质。如果还能松弛说明路径可以无限变短那一定有个环的权重之和是负的。写代码时可以在bellman_ford函数后面加一个checkbool check_negative_cycle() { for (int j 1; j m; j) { if (dis[e[j].a] e[j].w dis[e[j].b]) return true; if (dis[e[j].b] e[j].w dis[e[j].a]) return true; } return false; }不过要注意我这里存的是无向边所以每条边按两个方向检查。无向边一旦出现负权就相当于同时存在两个方向的负权边立刻构成负环。所以Bellman-Ford处理负权时通常默认是有向图。P1381没有负权所以这个扩展在这题用不到但以后做带负权边的题目会用上。5. SPFA队列优化的浪漫与陷阱5.1 实现细节与SLF/LLL优化SPFA是对Bellman-Ford的改进。Bellman-Ford每轮都要扫描所有边但很多时候大部分边并没有被松弛成功。SPFA的思路是只有那些在上一轮被更新过的点才可能在下一轮更新别人。所以用一个队列维护“待更新的点”初始时把起点放进去然后不断取出队首遍历它所有出边如果能松弛别人就把那个点放进队尾。代码#include bits/stdc.h using namespace std; const int N 100005; const int INF 0x3f3f3f3f; struct Edge { int v, w; }; int n, m; vectorEdge adj[N]; int dis[N]; int relaxed[N]; // 记录松弛成功次数 bool inq[N]; bool spfa() { memset(dis, 0x3f, sizeof(dis)); memset(inq, 0, sizeof(inq)); memset(relaxed, 0, sizeof(relaxed)); dis[1] 0; queueint q; q.push(1); inq[1] true; while (!q.empty()) { int u q.front(); q.pop(); inq[u] false; for (int i 0; i (int)adj[u].size(); i) { int v adj[u][i].v; int w adj[u][i].w; if (dis[u] w dis[v]) { dis[v] dis[u] w; relaxed[v]; if (relaxed[v] n) return false; // 存在负环 if (!inq[v]) { q.push(v); inq[v] true; } } } } return true; } int main() { cin n m; for (int i 1; i m; i) { int a, b, w; cin a b w; adj[a].push_back({b, w}); adj[b].push_back({a, w}); } bool ok spfa(); if (!ok) cout -1 endl; // 实际题目不会出现 else if (dis[n] INF) cout -1 endl; else cout dis[n] endl; return 0; }这里relaxed[v]记录的是节点v被松弛成功的次数。正常情况下一个点的最短距离最多被更新n-1次如果更新到n次说明存在负环。注意在无向负权图里SPFA一运行就会判负环这符合理论。如果你想让SPFA再快一点可以加SLF优化插入队首时如果新节点的当前距离比队首还小就插入队首。这个优化在随机图上效果不错但治标不治本。还有LLL优化取平均值判断写起来更复杂实战收益也有限。建议先把基础版本写对再考虑优化。5.2 卡SPFA的阴暗面我必须要泼一盆冷水SPFA的最坏复杂度是O(nm)而且真的可以被构造数据卡死。最常见的就是网格图每个点只和上下左右相连起点在左上角终点在右下角。这种图里SPFA的队列会让大量节点反复入队出队运行时间会让人怀疑人生。所以很多出题人会专门设计数据卡SPFA。这也是为什么现在的主流建议是如果题目说明边权非负优先用堆优化Dijkstra不要用SPFA去赌数据。如果题目有负权边那就只能用Bellman-Ford或SPFA但也要小心负环问题。这题P1381没有负权用SPFA只是练手。你心里要清楚它不是万能钥匙只是一个有历史意义、思路漂亮的算法。6. 四种做法对比与排错经验6.1 复杂度与适用场景表格我把四种做法的关键信息整理成一张表方便你刷题时快速决定用哪个算法时间复杂度空间复杂度适合场景能否处理负权能否检测负环朴素DijkstraO(n^2)O(n^2)n小且稠密的图否否堆优化DijkstraO(m log n)O(nm)稀疏图边权非负否否Bellman-FordO(nm)O(m)存在负权边且无负环的小图能能SPFA平均较快最坏O(nm)O(nm)随机图或检测负环能能怎么选第一步看n和m。n很大且m不大堆优化Dijkstra是默认选项。n很小怎么折腾都行。第二步看有没有负权边。有负权就避开Dijkstra选Bellman-Ford或者SPFA。第三步看会不会有负环。负环意味着没有“最短路”要先判出来。这题是典型测正确性的四种都能AC但我建议你至少把堆优化Dijkstra练熟因为它是未来竞赛最高频的写法。6.2 常见Bug清单最后给你一份我批改学生作业时随手记录的常见问题基本都是真实踩过的坑1. 初始化漏边。邻接矩阵要memset(g,0x3f,sizeof(g))输入时用min处理重边。如果忘了处理重边后面松弛时可能用较大值覆盖较小值直接让答案变差。2. 无向图只建一条边。堆优化和SPFA的邻接表里必须正反各加一次。Bellman-Ford里则必须对每条边做两个方向的松弛。3. INF选择不当。用0x3f3f3f3f而不是0x7fffffff原因前面说过避免两个INF相加溢出。如果你用long long就用0x3f3f3f3f3f3f3f3f或者干脆1e18。4. 堆优化忘记过滤旧状态。少了if (d ! dis[u]) continue;程序可能跑出正确结果但耗时成倍增长。在极端数据下会超时。5. 判断不可达的条件。用dis[n] INF来判断绝不能写成dis[n] -1因为你初始化的是一个大数不是-1。6. SPFA判负环的数组位置。有的同学把relaxed[v]写在if(!inq[v])里面只有入队时计数。这其实也能判但可能漏掉节点已经在队列中的更新情况。我习惯写在松弛成功之后逻辑更清晰。7. 边界n1。起点和终点相同最短路是0。这个边界在四种算法里都要注意尤其是在Bellman-Ford和SPFA里如果起点就是终点循环可能不会更新任何点但你得输出0而不是-1。我个人在实际操作中的体会是不要把最短路算法当作模板死背而是当成工具去理解。每学一个算法就回到P1381这道城市路上换一种写法重新提交一遍对比时间和感悟。这样刷完比盲刷二十道图论题都管用。最后再分享一个小技巧无论用哪种做法开数组、建图、初始化这三个步骤做完先跑一遍样例再自己构造一个最小数据比如n1或n2, m0验证边界最后再交评测。这个习惯能帮你拦下至少一半不该有的WA。