最短路径
01 / 共享的机制
从源点出发,到所有节点的最短距离。机制按边能携带什么分叉 —— 等权坍缩成 BFS,非负权要优先队列(Dijkstra),允许负权要做多轮松弛(Bellman-Ford), 全源距离则落到 Floyd-Warshall。
01 / 一句话本质
处理完中转点 k 之后,dist[i][j] 就是只允许把{0, …, k} 作为中转的 i 到 j 最短路径 —— 所以对 (k, i, j) 做三重循环,就把每一对节点扫到最终的最短距离。
题目带权图上的全源最短路图菱形V4
A
B
C
D
A
0
1
4
∞
B
1
0
∞
3
C
4
∞
0
1
D
∞
3
1
0
图有 4 个节点、8 条有向边。初始 dist:对角线 = 0,边对应位置 = 权重,其余 ∞。
步
0 / 137
k
—
(i, j)
—
最近更新
—
0 / 137
请在上方选择预设 —— Floyd-Warshall 是全源算法,不需要选择源点。
02 / 模式骨架
# Floyd-Warshall —— 全源最短路dist[i][j] ← ∞ for all i, jdist[i][i] ← 0 for all idist[u][v] ← w for each edge (u, v, w)# 三重循环:k 放最外层for k in [0, V):for i in [0, V):for j in [0, V):if dist[i][k] + dist[k][j] < dist[i][j]:dist[i][j] ← dist[i][k] + dist[k][j]# 第 k 轮结束后,k 就是允许的最大中转点编号
03 / 什么时候用这个模式
"全源最短路"
需要的是每一对节点之间的距离,而不是从单一源点出发。对每个点跑一次 Dijkstra 要 O(V · (V + E) log V);Floyd-Warshall 用 O(V³) 就能算完,内层只有两行。
"小而稠密的图"
V 很小(最多几百)。三次方代价占主导,但常数因子极低 —— Floyd 的热路径只有几次数组读取和一次比较。
"传递闭包 / 可达性矩阵"
把
+ 换成 OR、min 换成 AND, 同一个三重循环就在算哪些点对相连。结构相同,只是换了半环。"链式比率 / 乘积型路径"
只要「路径代价」用某个可结合的算子来合成(比率相乘、按位与、最小值取最大), Floyd 的三行更新就可以推广 —— 换算子,结构不变。
04 / 常见坑
i.
把
k 写在不是最外层的位置。DP 不变式 —— 「dist[i][j] 只用 {0…k} 里的中转点」 —— 成立的前提是每个 (i, j) 都先把 k 处理完才进入下一个 k。 一旦把 k 放进去,部分答案和最终答案就会混在一起,结果就错了。
ii.
把
∞ + x 当成普通数。实际代码里
INT_MAX + w 会溢出。要么用 1e9 这种哨兵值, 要么在加之前加判断 if dist[i][k] != ∞ and dist[k][j] != ∞。 本动画里直接写 ∞ 是为了矩阵可读。iii.
忘了负环会让结果失效。
只要负环不可达,Floyd 在有负边的情况下依然正确。 算完后若存在某个 i 使
dist[i][i] < 0, 就说明有负环 —— 看一眼对角线就能发现。05 / 去 LeetCode 上练习
四道题,按难度排序。这里有意不放解答。
— / 什么时候用哪个
无权 BFS
当每条边的代价相同时使用 —— 一步 = 一条边。
网格 · 迷宫 · O(V + E)
Dijkstra
当边权非负时使用。
优先队列 · O((V + E) log V)
Bellman-Ford
当允许负权,或需要检测负环时使用。
V−1 轮松弛 · O(V · E)
Floyd-Warshall
当需要全源距离、而不仅是单源时使用。
经中转点 DP · O(V³)