最短路径
01 / 共享的机制
从源点出发,到所有节点的最短距离。机制按边能携带什么分叉 —— 等权坍缩成 BFS,非负权要优先队列(Dijkstra),允许负权要做多轮松弛(Bellman-Ford), 全源距离则落到 Floyd-Warshall。
01 / 一句话本质
当每条边的代价都相同时,第一次到达某个节点就是到达它的最短方式 —— 所以 BFS(按步数递增顺序访问节点)天然就是最短路径算法。
题目无权图上,从源点到所有节点的最短路径图网格源点A
图有 6 个节点。把所有距离初始化为 ∞,把源点放入队列。
步
0 / 40
队列
—
已访问
0 / 6
0 / 40
02 / 模式骨架
# 从源点出发的 BFS —— 每条边权 = 1dist[v] ← ∞ for all vdist[s] ← 0queue ← [s]while queue 非空:u ← queue.pop_front()for v in neighbors(u):if dist[v] = ∞:dist[v] ← dist[u] + 1; queue.push(v)# 第一次访问 = 最短距离,因为队列是按层向外清空的
03 / 什么时候用这个模式
"无权图"
边没有权重,或所有权重相同。网格里每步走一格也算 —— 网格只是一个隐式的图。权重一旦不同,BFS 就不再给出最短路径。
"最少步数"
目标是数跳数而非代价。「最少操作数」「最少移动」「最短序列」都是同一类。
"迷宫最短路径"
网格类问法。4-邻接(或 8-邻接)让每一格的移动恰好是一步。
"多源 BFS"
把所有源点都以距离 0 一起入队,跑一次 BFS —— 比对每个源点单独跑一次便宜得多。
04 / 常见坑
i.
「DFS 更简单」就选了 DFS。
DFS 是按某种顺序访问,不是按距离顺序;它第一次到达节点的路径可能很长。 无权最短路径必须用 BFS。
ii.
在出队时才标记已访问,而不是入队时。
如果只在
v 出队时才标记 visited[v] = true, 同一个节点可能在队列里出现很多次 —— 在稠密图上会平方级膨胀。入队时就标记。iii.
忘了 BFS 只适用于非负、等权的图。
边权一旦不同,BFS 就会给出错误答案。这时要用 Dijkstra (或当权值只能是 0/1 时,用双端队列做 0-1 BFS)。
05 / 去 LeetCode 上练习
四道题,按难度排序。这里有意不放解答。
— / 什么时候用哪个
无权 BFS
当每条边的代价相同时使用 —— 一步 = 一条边。
网格 · 迷宫 · O(V + E)
Dijkstra
当边权非负时使用。
优先队列 · O((V + E) log V)
Bellman-Ford
当允许负权,或需要检测负环时使用。
V−1 轮松弛 · O(V · E)
Floyd-Warshall
当需要全源距离、而不仅是单源时使用。
经中转点 DP · O(V³)