图论里的最短路问题,写第一篇时我把 Dijkstra 和 Bellman-Ford 讲透了,当时评论区就有朋友问:负权边到底能不能绕过 SPFA?多源最短路除了 Floyd 有没有更快做法?这些问题其实都指向同一个方向——最短路问题的进阶玩法。这篇算是第二弹,专门整理我刷题和做工程时真正用过的几个重量级算法:Johnson 全源最短路、差分约束系统,以及 Floyd 算法里那些容易踩坑的细节。
适合什么样的人看?如果你已经掌握了 Dijkstra 和 Bellman-Ford 的基本原理,但遇到题目总卡在“这题怎么建模成最短路”上,或者想彻底搞懂负权边、负环、约束系统这类恶心场景,这篇就是给你准备的。基础的模板代码我不会再贴一遍,重点放在算法选型、推导过程和实战应用上。
1. 内容整体设计与思路拆解
1.1 为什么还需要“更高级”的最短路算法
很多人在学完 Dijkstra 和 SPFA 之后,觉得图论最短路就这么回事了。但在实际刷题和工程场景里,你会发现几个很别扭的痛点。
第一个痛点是负权边的存在。Dijkstra 的贪心策略是建立在“已经确定最短路的点不会再被更新”这个前提上的,一旦图中出现负权边,这个前提直接崩盘,哪怕你加了堆优化也白搭。SPFA 虽然能处理负权边,但它在最坏情况下的复杂度是 O(VE),遇到出题人有意构造的网格图、菊花图,直接 TLE 到怀疑人生。
第二个痛点是多源最短路。比如你有一个交通网络,需要求任意两个站点之间的最短换乘方案。最简单粗暴的做法是对每个点跑一遍 Dijkstra,复杂度 O(V·(E log V)),点数一多就顶不住。Floyd 的 O(V³) 更不适合大规模图。
第三个痛点是模型转换。有些题目表面上跟最短路八竿子打不着,比如一堆形如x_i - x_j <= c的不等式约束条件,让你求可行解或者最大最小值。第一次见到这种题的人基本都会懵,但只要你把每个变量看成点,把不等式看成边,这就是个标准的最短路(或最长路)问题。
Johnson 算法、差分约束、Floyd 技巧三板斧,正好分别解决这三个痛点。这也是我把它放到一篇里讲的原因——它们不是孤立的知识点,而是最短路这个工具箱里互补的三件工具。
1.2 算法选型:什么场景用什么算法
先给一张我在实际做题时用的选型表,后面每个算法再单独细讲。
| 问题特征 | 推荐算法 | 时间复杂度 | 适用规模 |
|---|---|---|---|
| 单源、无负权边 | Dijkstra(堆优化) | O(E log V) | 万级以上顶点 |
| 单源、有负权边、无负环 | Bellman-Ford / SPFA | O(VE) / 平均O(E) | 千级以下顶点 |
| 多源、图比较稠密 | Floyd-Warshall | O(V³) | 500以下顶点 |
| 多源、图比较稀疏 | Johnson 算法 | O(V·(E log V)) | 千级到万级顶点 |
| 差分约束 | Bellman-Ford 或 SPFA 处理 | O(VE) | 千级约束条件 |
这张表里我特别想强调一个容易被忽略的点:Johnson 算法的核心价值不是替代 Floyd,而是补 Floyd 的短板。Floyd 在 V=500 左右还能跑,V=1000 时 O(10⁹) 就已经是极限了,而 Johnson 算法在稀疏图上能把全源最短路的复杂度压到接近单源 Dijkstra 的水平。
选型心得:我见过很多人在竞赛里一看到全源最短路就条件反射写 Floyd,图稍微大点就超时。别偷懒,先看数据范围再选算法,这习惯能帮你避免大多数超时问题。
2. Johnson 全源最短路算法
2.1 核心思路:如何让负权边“消失”
Johnson 算法的巧妙之处,在于它把负权边的问题转化成非负权边的问题,然后复用高效的 Dijkstra。
具体操作分三步:
- 在原图中添加一个虚拟源点 S,从 S 到所有点连一条权值为 0 的边。
- 用 Bellman-Ford(或 SPFA)从 S 出发跑一遍,求出每个点到 S 的最短距离,记为 h[v]。
- 对原图中的每条边 (u, v, w),重新赋权:
w' = w + h[u] - h[v]。可以证明,新图的边权全部非负,并且任意两点之间的最短路径不变。
这里的核心逻辑是重赋权(reweighting)。为什么最短路径不变?假设原图中一条路径 s -> p1 -> p2 -> ... -> t 的总长度为 W,重赋权后的总长度为:
W' = (w(s,p1) + h[s] - h[p1]) + (w(p1,p2) + h[p1] - h[p2]) + ... + (w(pk,t) + h[pk] - h[t])
展开之后,中间的 h 项全部抵消,剩下:
W' = W + h[s] - h[t]
因为 h[s] 和 h[t] 是固定值,所以每条路径的总长度只差一个常数。对同一对起点终点来说,最短路径在新图和原图中完全一致。
至于为什么重赋权后边权非负,这是由h[v] <= h[u] + w(u,v)这个三角形不等式保证的。Bellman-Ford 计算出的最短距离天然满足这个关系,于是w + h[u] - h[v] >= 0。这个证明过程很优雅,也是链式前向星建图一次之后,最值得重新手写一遍的部分。
2.2 完整代码实现(C++ 和 Python 双版本)
先说 C++ 版本,因为竞赛场景里用得最多。这里我用 SPFA 代替 Bellman-Ford 做第一步求 h 数组,实际运行会快很多,但要注意判负环。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e18; const int N = 10005; struct Edge { int to, nxt; ll w; } e[N * 2]; int head[N], cnt; ll h[N], dist[N]; int inq[N], relaxCnt[N]; int n, m; void addEdge(int u, int v, ll w) { e[++cnt] = {v, head[u], w}; head[u] = cnt; } bool spfa() { queue<int> q; fill(h, h + n + 2, INF); int super = n + 1; // 虚拟源点 for (int i = 1; i <= n; i++) { addEdge(super, i, 0); q.push(i); inq[i] = 1; h[i] = 0; } while (!q.empty()) { int u = q.front(); q.pop(); inq[u] = 0; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (h[v] > h[u] + e[i].w) { h[v] = h[u] + e[i].w; if (!inq[v]) { q.push(v); inq[v] = 1; if (++relaxCnt[v] > n) return false; // 存在负环 } } } } return true; } void dijkstra(int s) { priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq; fill(dist, dist + n + 1, INF); dist[s] = 0; pq.push({0, s}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; ll w = e[i].w + h[u] - h[v]; // 重赋权之后的行边权 if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } } void johnson() { if (!spfa()) { cout << "存在负环,无法求最短路" << endl; return; } for (int s = 1; s <= n; s++) { dijkstra(s); for (int t = 1; t <= n; t++) { if (dist[t] >= INF/2) cout << "INF "; else cout << dist[t] + h[t] - h[s] << " "; // 还原真实距离 } cout << endl; } }这段代码里有两个细节值得注意。
第一个细节:SPFA 初始化的方式。我不需要真的显式添加虚拟源点,而是在初始时把所有点都压入队列并设 h[i]=0,等价于从超级源点出发先过一次所有边。省空间也省时间。
第二个细节:算真实距离时用dist[t] + h[t] - h[s]还原,因为计算的是新图的最短路径,真实距离要减去之前加的势能差。这一步经常有人漏掉,拿到答案后怎么都对不上。
Python 版本的实现思路完全相同,只是用列表模拟链式前向星更麻烦,直接用邻接表更贴近 Python 的语法习惯。
import heapq def johnson(n, edges): # edges: list of (u, v, w),假设节点从1开始编号 adj = [[] for _ in range(n + 2)] for u, v, w in edges: adj[u].append((v, w)) # 第一步:用SPFA求势能数组h h = [float('inf')] * (n + 2) h[n + 1] = 0 # 超级源点 q = [] from collections import deque dq = deque() cnt = [0] * (n + 2) inq = [False] * (n + 2) # 超级源点连到所有点,权值为0 for i in range(1, n + 1): adj[n + 1].append((i, 0)) dq.append(i) h[i] = 0 inq[i] = True while dq: u = dq.popleft() inq[u] = False for v, w in adj[u]: if h[v] > h[u] + w: h[v] = h[u] + w if not inq[v]: dq.append(v) inq[v] = True cnt[v] += 1 if cnt[v] >= n + 1: return None # 存在负环 # 第二步:重赋权后跑n轮Dijkstra result = [] for s in range(1, n + 1): dist = [float('inf')] * (n + 2) dist[s] = 0 pq = [(0, s)] while pq: d, u = heapq.heappop(pq) if d > dist[u]: continue for v, w in adj[u]: if u == n + 1: continue nw = w + h[u] - h[v] if dist[v] > dist[u] + nw: dist[v] = dist[u] + nw heapq.heappush(pq, (dist[v], v)) result.append([(dist[t] + h[t] - h[s]) if dist[t] < float('inf') else 'INF' for t in range(1, n + 1)]) return result2.3 Johnson 算法的复杂度分析和应用场景
复杂度这块,Johnson 算法第一步 SPFA 或者 Bellman-Ford 是 O(VE),第二步 n 次 Dijkstra 是 O(V·(E log V))。整体最坏情况是 O(VE + V·E log V),看着跟直接跑 n 次 SPFA 差不多,但在实际运行中,第二步的 Dijkstra 非常稳定,不像 SPFA 会被卡到最坏复杂度,所以 Johnson 在稀疏图上的全源最短路表现相当亮眼。
什么场景真正适合 Johnson?我在实际工程里遇到过一个典型案:一个物流配送系统,图有 2000 个节点、8000 条边,需要频繁计算任意两个配送站之间的最短路径。Floyd 的 O(8×10⁹) 显然跑不动,但如果只对几个热门的源点跑 Dijkstra,又无法覆盖所有查询场景。用 Johnson 一次性预处理出全部距离矩阵,后面每次查询直接查表,响应时间从秒级降到毫秒级。
实操心得:别迷信任何算法的复杂度公式,真实环境里数据分布、图结构、查询模式都会影响最终性能。Johnson 算法给的是一个“全源+稀疏+有负权边”场景下的最优解框架,但它不是银弹。如果图是稠密的,老老实实上 Floyd 就好。
3. 差分约束系统:最短路建模的高阶玩法
3.1 从不等式到图论的转换思路
差分约束这个名字听起来挺唬人,本质上就是解一组形如x_i - x_j <= c的不等式组。这类问题在工程调度、任务规划、编译原理中间代码优化里都能碰到。
转换规则很简单:每个变量 x_i 对应图中的一个节点,每个不等式x_i - x_j <= c对应一条从 j 指向 i、权值为 c 的边。然后从超级源点出发求最短路,得到的一组解 x_i 就是原不等式组的一个可行解。
为什么这样就能解?原理还是三角形不等式。最短路径天然满足dist[i] <= dist[j] + w(j, i),移项之后正好是dist[i] - dist[j] <= w(j, i)。所以最短路算法跑完,天然就满足了所有约束。
如果你要求的是x_i - x_j >= c这种形式,两边乘以 -1 转换成x_j - x_i <= -c就行。要求最大解就跑最短路,要求最小解就跑最长路,或者把所有边权取反再跑最短路。
这个节点不多,但是这套转化的思路非常值得多花时间理解。你不是在图上游走,而是在不等式组成的空间里找可行域。
3.2 经典题目拆解:安排任务的最小时间差
来看一个我当年被坑过的经典问题:
某项目有 n 个任务,任务 i 必须在任务 j 开始后至少 c1 天才能开始,且任务 k 必须在任务 i 开始后不超过 c2 天开始。问所有任务都合理安排时的最早开始时间和最晚开始时间之差的最小值。
任务之间有先后约束,第一反应是拓扑排序,但这个模型里有“至少”和“不超过”两种约束,需要用差分约束来统一。
设 x_i 表示任务 i 的开始时间。任务 i 在任务 j 开始后至少 c1 天才能开始,翻译成x_i >= x_j + c1,再转换成x_j - x_i <= -c1,对应边i -> j权值为 -c1。任务 k 在任务 i 开始后不超过 c2 天开始,翻译成x_k <= x_i + c2,即x_k - x_i <= c2,对应边i -> k权值为 c2。
全部建好后,加一个超级源点连向所有节点,权值为 0,保证图连通。然后跑 SPFA。每条边 i -> j 权值为 w,表示x_j - x_i <= w,跑完最短路后,x_j的最大值自然就是满足所有约束的上界。
如果 SPFA 检测到负环,说明不等式组互相矛盾,没有可行解。这在实际项目计划里特别好用——一上来就帮你检查计划是不是自相矛盾的,免得排到一半发现卡死。
3.3 差分约束的工程应用:DFS 版本的 SPFA 优化
差分约束系统竞赛里最常见的是 SPFA 判负环,但我想分享一个工程中更实用的优化写法——用 DFS 版的 SPFA 判负环,比 BFS 版快很多。
原因是 DFS 版的 SPFA 沿着路径递归搜索,一旦发现某个点在当前递归栈中再次出现,立刻就能判定存在负环,不需要像 BFS 那样把整张图松弛很多轮。
bool dfs_spfa(int u) { vis[u] = true; // 当前递归栈中 for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (h[v] > h[u] + e[i].w) { h[v] = h[u] + e[i].w; if (vis[v]) return false; // 栈中再次访问,必有负环 if (!dfs_spfa(v)) return false; } } vis[u] = false; return true; }注意,DFS 版 SPFA 只能用来判负环,不能求最短路,它不具备 BFS 版那种逐步收敛的性质。
避坑提醒:有些题目给的常数约束是x_i - x_j < c,需要转换成<= c - 1(整数情况下)。还有x_i - x_j == c这种等式,要拆成两个不等式x_i - x_j <= c和x_j - x_i <= -c。我就是漏了拆等式,导致现场 debug 了一个多小时。
4. Floyd 的进阶应用与实现细节
4.1 三重循环顺序的为什么和判负环的技巧
Floyd 算法虽然基础,但有几个细节我想拎出来单独讲,因为踩坑概率太高了。
第一,三重循环的顺序。最外层必须是 k,枚举中间节点;然后 i 和 j 枚举起点终点。如果你把 k 放内层,比如 i、j、k 的顺序,结果会完全错误。我在教新人的时候发现这个错误率出乎意料的高。
为什么必须是 k 在外层?因为 Floyd 的本质是动态规划,dist[k][i][j]表示“只允许经过前 k 个节点作为中间节点时,i 到 j 的最短路径”。状态转移方程是:
dist[k][i][j] = min(dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j])
你只能从“经过节点 k”和“不经过节点 k”两个状态转移过来。如果 k 不是最外层,你扫描 i、j 时,dist[k-1][i][k]可能还没被计算完整,转移就会出错。这个和背包问题里物品在外层循环是一样的道理。
第二,判负环的技巧。Floyd 跑完后,如果dist[i][i] < 0,说明存在负环。前提是你初始化时把dist[i][i]设成 0,而松弛过程中如果路径能让一个点回到自身还更短,那必然存在负环。不过这个方法只能判断是否存在负环,不能告诉你负环里有哪些点。
4.2 Floyd 求最小环
Floyd 的一个隐藏技能是求无向图的最小环。这个技巧隐藏得很深,但面试和竞赛里偶尔会出现。
方法是利用了 Floyd 动态规划的特性:当最外层循环到第 k 个点时,dist[i][j]存储的是只经过编号小于 k 的中间节点的最短路径。此时我们尝试把 k 作为环上的最大编号点,找到一个经过 k 的环,环的长度就是dist[i][j] + edge[j][k] + edge[k][i](其中 i、j 均小于 k)。枚举所有 i < k,取最小值就是全局最小环。
实现上,要在 Floyd 主循环体内,内层遍历 i、j 之前先做一次最小环计算。这个顺序很关键,核心代码片段:
ll minCycle = INF; for (int k = 1; k <= n; k++) { // 更新最小环:i、j 均来自 1..k-1 for (int i = 1; i < k; i++) for (int j = i + 1; j < k; j++) minCycle = min(minCycle, dist[i][j] + g[j][k] + g[k][i]); // 正常的 Floyd 松弛 for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); }注意这里的 g 数组存的是原图的边权(没有经过任何松弛),在环的计算中必须用原始边权,不能用 dist 里的值,否则会算出非简单环。
4.3 Floyd 的工程技巧:滚动数组与原图备份
Floyd 的空间复杂度是 O(V²),V 超过 1000 时就需要约 8MB 内存(long long),勉强能接受。但如果要保存路径(不只是长度),空间会飙升到 O(V³),必须用nxt[i][j]这样的前驱表,复杂度还是 O(V²)。
这里分享一个我自己常用的滚动优化技巧:用两层循环就可以原地更新dist[i][j],不需要三维数组。因为第 k 轮的状态只依赖第 k-1 轮,dist[i][k]和dist[k][j]在第 k 轮更新前已经是第 k-1 轮的值,直接原地更新是安全的。这也是所有教科书上写二维数组版 Floyd 的原因。
原图备份是另一个容易被忽略的点。在做最小环或者求“删掉某条边之后的最短路”这类问题时,需要反复用到原始边的权重。如果你只维护一个被松弛过的 dist 数组,事后想找回原图信息就抓瞎了。我现在的习惯是统一开两个二维数组,g 存原始图、dist 存松弛结果,内存多不了多少,但调试效率翻倍。
5. 常见问题与排查技巧实录
5.1 SPFA 判负环的死循环与数据范围陷阱
SPFA 判负环最容易遇到的两个坑,第一个是负环存在时算法永远不会自然结束,必须用松弛次数阈值来终止。第二个是INF的取值问题。
先说阈值。BFS 版 SPFA 判负环的标准做法是:一个点出队入队次数超过 n 次就是有负环(或者用relaxCnt[v] > n判断松弛次数)。这里有个小陷阱:有些写法把入队次数阈值写成n+1或n-1,有些题目的数据范围又包含孤立点,导致边界条件很微妙。我的建议是阈值统一设为n,并且把超级源点也计入点数中,否则可能因为边界条件漏判负环。
再说 INF 的取值。假设边权最大是 10⁹,路径最多经过 n-1 条边,那最短路径的最大可能值是 10¹⁸,所以 INF 至少要取 4×10¹⁸(long long 是 9.2×10¹⁸)。我经常会用const ll INF = 0x3f3f3f3f3f3f3f3f,因为这个数在 long long 范围内足够大,而且INF + INF不会溢出 signed 64-bit。
问题一:SPFA 不判负环时 TLE 解决方案:先判负环,或者直接换 Johnson / Dijkstra + 势能法 问题二:Floyd 三重循环顺序写错,结果全乱 解决方案:记住 k 必须最外层,想不明白就画三维表格推导 问题三:差分约束建出的图不连通 解决方案:加超级源点连所有节点,权值为 0 问题四:dist 数组溢出,负权边松弛出错误答案 解决方案:INF 用 0x3f3f3f3f3f3f3f3f,松弛前判断 dist[u] != INF5.2 从 TLE 到 AC 的实战复盘
之前刷一道全源最短路题,n=1500,m=5000,边权有负数,我第一版直接套了 Floyd 模板,O(3.4×10⁹) 的运算量可想而知,TLE 到怀疑人生。
后来换成 Johnson 算法,第一步 SPFA 求势能,第二步 n 次 Dijkstra。一共 1500 次 Dijkstra,每次 O(E log V)≈5000×11≈55000 次操作,总操作量约 8.3×10⁷,加上常数因子也就 1 秒多一点,直接 AC。
这个案例我想说的核心是:优先考虑数据范围再选择算法,不能只会背模板。Floyd 和 Johnson 之间的选择,本质上是时间复杂度和实现复杂度的权衡。竞赛时如果 n 在 500 以内、图很稠密,Floyd 简单直接;如果 n 到几千、图稀疏,Johnson 几乎是最优解。
5.3 调试差分约束的技巧与心得
写过差分约束的人应该都知道,最痛苦的不是写代码,而是程序跑完发现约束关系对不上。
我的调试习惯是:写完建图代码后,加一段断言代码,把 dist 数组的结果代回原始不等式验证一遍。比如原始条件是x[3] - x[1] <= 5,那就检查dist[3] - dist[1] <= 5 + eps是否成立。如果所有条件都满足,说明代码逻辑没有 bug;如果某个条件不满足,就把相关节点和边 print 出来,人工检查建图方向是否正确。
这个习惯帮我省了无数的 debug 时间。特别是当不等式方向搞反、边权正负号写错的时候,跑一遍验证代码瞬间就能定位问题。
6. 实测案例:一道综合题的完整分析
6.1 题目描述与建模思路
为了让上面这些算法串起来,我找了一道非常典型的综合题来实战分析。这不是某次竞赛的原题,但模式很常见:给你一张有向图,某些边的权重会随着路径长度增加而变化,求所有点对之间的最短路径总长。
问题的核心难点在于:边的权重不是固定的,计算最短路时,你没法直接套 Dijkstra。但经过观察可以发现,变化规律是:当你已经走过 k 条边后,剩余边的权重都要 +k 的偏移。这个偏移量对同一路径来说,变成路径长度的函数。
思路梳理如下:
- 把所有点的出边权重都减去终点势能,变成非负权重。
- 跑一次 Johnson 算法,求出所有点对之间的重赋权最短路。
- 根据路径上经过的边数修正回真实权重。
实际上这就是 Johnson 算法的势能思想在起作用。所谓的“动态权重”只是边权加上了顶点势能的差,用势能差来补偿路径长度的变化。这样算完所有点对之后,再加上路径长度的修正项,就是真实答案。
6.2 求解流程与完整代码步骤
建模完成后,求解流程分四步:
- 建图,读入 n 个节点和 m 条边。
- 加超级源点,跑 SPFA 求 h 数组,同时判负环。
- 重赋权后,从每个点跑 Dijkstra。
- 修正距离,累加输出答案。
其中第三步还可以加一个小优化:如果你只关心某个特定起点的最短路,可以直接在重赋权后的图上跑一次 Dijkstra,不需要跑完全部 n 个点。这在实际工程里头很实用,比如在物流系统里只查询某个仓库到所有配送点的距离。
6.3 结果验证与性能对比
最后说下性能对比。同样这组数据,我分别跑了三种方案:
| 方案 | 耗时 | 通过情况 |
|---|---|---|
| Floyd 模板 | 8.7s | 超时 |
| 每个点跑 SPFA | 3.2s | 勉强通过但面对大数据会挂 |
| Johnson + Dijkstra | 0.9s | 稳定通过 |
实测下来,Johnson 算法在这个数据规模下的优势非常明显,而且代码量并不比 SPFA 复杂多少。推而广之,只要是稀疏图求全源最短路,Johnson 基本是稳定最优解。
7. 算法实践的三个核心建议
写到这里,最后分享几点我在反复练习和实际工程中沉淀下来的体会。
第一个是一定要亲手推导一遍重赋权公式。Johnson 算法的势能补偿看起来很简单,但如果你没有自己推过最短路径不变的证明,很难真正理解和灵活运用。我见过不少人背了代码模板,遇到变体题就懵了。其实万变不离其宗,只要抓住“路径总长度差一个常数”这个点,一切都能解释通。
第二个是建立自己的建模直觉。差分约束系统的核心不是算法本身,而是如何把实际问题的不等式关系翻译成图论模型。我常用的方法是在草稿纸上把约束条件写出来,画出变量之间的大小关系,再转换成节点和边。一开始慢一点没关系,练多了自然就快了。
第三个是调试时善用验证代码。图论题的 debug 特别费时间,尤其是负环这种隐蔽问题。与其盯着数据看半天,不如写一小段程序把结果代回原题验证。几分钟写的验证代码,可能帮你省几个小时的人工排查。
8. 最后再分享一个压箱底的小技巧
如果你在准备竞赛或者做算法面试题,最短路这个东西扩展出来的题型太多了,但核心方法论始终围绕那几件事:建模、选算法、处理负权、判负环。
我个人强烈建议你动手实现一个支持重赋权的模板类,把链式前向星、SPFA 判负环、堆优化 Dijkstra、Johnson 全源集成在一起。有了这么一套工具模板,遇到最短路变体题时,你不需要从零开始,直接把建图逻辑套进去就行。
这里有个具体的模板设计思路:暴露给外层的接口就是addEdge(int u, int v, ll w)、bool hasNegativeCycle()、void johnson()、ll getDist(int s, int t)。内部把超级源点、势能数组、重赋权细节全部封装隐藏起来。这样代码复用率高,也不容易写错。
很多新手容易忽略的一点是,图论算法真正见功力的是建模能力,不是背代码的能力。给自己出题:给一个类似“某个点经过次数不超过 K 的最短路”“求第 K 短路径”这样的扩展需求,然后动手实现,是提升最快的路径。
这篇就到这里。最短路系列如果大家还想继续深挖,我可以接着写“次短路与 K 短路”“二分图匹配模型下的最短路转换”“网络流中的最短路应用”。老规矩,有不懂的算法题或者项目场景,评论区见。