02.4.2.4 最短路径与最小生成树
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.4 树与图 / 02.4.2 图论与并查集
02.4.2.4-001 最短路径问题分哪几类?
一句话结论
按需求分:无权图最短路(BFS)、单源最短路(Dijkstra/Bellman-Ford)、全源最短路(Floyd);按权值分非负权与含负权;按图型分一般图与 DAG。
概念解释
- 单源:一个起点到各点。
- 全源:所有点对。
- 权值:是否允许负边。
原理流程
- 明确起点数量。
- 判断边权正负。
- 选算法。
代码 / 图示
无权 → BFS
单源非负 → Dijkstra
单源负权 → Bellman-Ford
全源 → Floyd
常见误区
- 误区:Dijkstra 可处理负权;正解:负权需 Bellman-Ford/SPFA。
- 误区:BFS 可求加权最短路;正解:BFS 只按边数分层。
追问
- Q:负环是什么? A:边权和为负的环,可无限降低路径代价。
- Q:DAG 最短路? A:拓扑序上 DP,O(V+E)。
02.4.2.4-002 无权图最短路为什么用 BFS?
一句话结论
无权图每条边代价 1,BFS 按距离逐层扩展,首次到达某顶点的层数即最短边数;DFS 不保证首达最短;O(V+E) 时间 O(V) 队列。
概念解释
- 边代价相同。
- 层序 = 距离。
- 首达最短。
原理流程
- 起点距离 0 入队。
- 逐层扩展。
- 未访问记录距离。
代码 / 示例
int[] dist = new int[n];
Arrays.fill(dist, -1);
dist[start] = 0;
Queue<Integer> q = new ArrayDeque<>();
q.offer(start);
while (!q.isEmpty()) {
int u = q.poll();
for (int v : g[u]) if (dist[v] == -1) {
dist[v] = dist[u] + 1; q.offer(v);
}
}
常见误区
- 误区:DFS 记录路径最短;正解:DFS 路径不保证最短。
- 误区:重复访问刷新距离;正解:首达即最短,标记即可。
追问
- Q:网格最短步数? A:四方向 BFS,见 02.4.2.1-015 同类。
- Q:多源最短路? A:所有源距离 0 同时入队。
02.4.2.4-003 Dijkstra 基本思路是什么?
一句话结论
贪心维护已确定最短路的集合;每次从未确定顶点中取距离最小者加入确定集,松弛其邻接边;非负权下贪心选择正确;O((V+E) log V) 堆实现。
概念解释
- 已确定集合。
- 贪心取最小距离。
- 松弛后继。
原理流程
- 起点距离 0,其余无穷。
- 取未确定最小距离点。
- 松弛邻接,更新距离。
代码 / 图示
dist[s]=0;其余 ∞
选 min dist → 确定 → 松弛
常见误区
- 误区:先确定所有点再松弛;正解:逐点确定逐点松弛。
- 误区:堆中保留过期条目;正解:弹出时距离不符则跳过。
追问
- Q:松弛公式? A:
dist[v]=min(dist[v], dist[u]+w(u,v))。 - Q:为什么贪心正确? A:非负权下不会经未确定点得到更短路径。
02.4.2.4-004 Dijkstra 堆实现怎么做?
一句话结论
小顶堆存 (距离, 顶点);起点入堆;弹出最小距离,已确定则跳过;否则松弛邻接,更优则更新距离并入堆;O((V+E) log V) 时间 O(V) 堆。
概念解释
- 堆:取最小距离。
- 惰性删除:过期条目跳过。
- 邻接松弛。
原理流程
- 距离数组初始化。
- 堆起点入队。
- 弹出、跳过旧条目、松弛。
代码 / 示例
int[] dijkstra(int start, List<int[]>[] g, int n) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.offer(new int[]{start, 0});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int u = cur[0], d = cur[1];
if (d > dist[u]) continue; // 过期条目
for (int[] e : g[u]) {
int v = e[0], w = e[1];
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.offer(new int[]{v, dist[v]});
}
}
}
return dist;
}
常见误区
- 误区:弹出条目不判过期;正解:
d > dist[u]跳过。 - 误区:邻接表存点未存权;正解:存
(v, w)二元组。
追问
- Q:堆中重复条目? A:惰性保留,过期跳过。
- Q:不用堆的 Dijkstra? A:线性扫描取最小 O(V²),稠密图可用。
02.4.2.4-005 Dijkstra 为什么要求非负权?
一句话结论
贪心假设当前最小距离点不会再被更短路径更新;负权边可能让后续路径更短,打破该假设;含负权用 Bellman-Ford;存在负环无最短路。
概念解释
- 贪心前提。
- 负权反例。
- 算法边界。
原理流程
- 非负:已选点距离已定。
- 负权:后到路径可能更短。
- 贪心失效。
代码 / 图示
选定点 u 后,负权边 v→u 可能使 dist[u] 变小
常见误区
- 误区:负权边不多就可用 Dijkstra;正解:只要有负权就可能失效。
- 误区:负环可求最短路;正解:负环上代价无限降低,无最短路。
追问
- Q:零权边可以吗? A:可以,非负含零。
- Q:无负边但有环? A:Dijkstra 正常。
02.4.2.4-006 Dijkstra 复杂度怎么算?
一句话结论
堆实现 O((V+E) log V):每条边至多触发一次堆更新,堆操作 log V;数组线性取最小 O(V²),稠密图更优;空间 O(V+E) 存图 + O(V) 堆/距离。
概念解释
- 堆操作对数。
- 边触发更新。
- 稠密取舍。
原理流程
- 统计边数。
- 堆操作次数 ≤ E。
- 标注存图与堆空间。
代码 / 图示
堆:O((V+E) log V)
数组:O(V²)
常见误区
- 误区:Dijkstra O(V+E);正解:堆取最小带 log V。
- 误区:每条边多次入堆导致 O(E log E);正解:条目数 ≤ E,量级同阶。
追问
- Q:斐波那契堆? A:理论 O(E+V log V),工程少用。
- Q:稠密图选哪种? A:数组版 O(V²) 免堆开销。
02.4.2.4-007 Bellman-Ford 怎么处理负权?
一句话结论
对所有边松弛 V-1 轮:每轮尝试 dist[v]=min(dist[v], dist[u]+w);V-1 轮后再松弛一轮仍能更新说明存在负环;O(VE) 时间 O(V) 空间。
概念解释
- 逐轮松弛。
- V-1 轮收敛。
- 负环检测。
原理流程
- 距离初始化。
- 重复 V-1 轮松弛全部边。
- 再松弛一轮判负环。
代码 / 示例
Arrays.fill(dist, INF); dist[s] = 0;
for (int i = 0; i < n - 1; i++) {
boolean updated = false;
for (int[] e : edges) {
if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]]) {
dist[e[1]] = dist[e[0]] + e[2]; updated = true;
}
}
if (!updated) break;
}
// 再松弛一轮仍更新 → 负环
常见误区
- 误区:只松弛一轮;正解:最长路径 V-1 条边,需 V-1 轮。
- 误区:负环仍返回距离;正解:报告负环无解。
追问
- Q:SPFA 是什么? A:Bellman-Ford 队列优化,只处理更新过的点。
- Q:负环一定可检测? A:可达负环可检测。
02.4.2.4-008 Floyd-Warshall 全源最短路怎么做?
一句话结论
邻接矩阵存距离;三重循环 中间点 k → 起点 i → 终点 j,松弛 dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j]);O(V³) 时间 O(V²) 空间,支持负权(无负环)。
概念解释
- 全源:点对距离。
- 中间点枚举。
- 动态规划。
原理流程
- 矩阵初始化直连边权。
- 枚举中间点松弛。
- 结果矩阵即全源距离。
代码 / 示例
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
常见误区
- 误区:循环顺序 i,j,k;正解:k 必须在最外层。
- 误区:Floyd 支持负环;正解:负环上距离无意义。
追问
- Q:Floyd 适用规模? A:V 较小(百级),O(V³)。
- Q:求路径怎么记? A:前驱矩阵记录中转。
02.4.2.4-009 最小生成树是什么?
一句话结论
连通无向图的生成树包含全部 V 个顶点、V-1 条边且无环;最小生成树(MST)是边权总和最小的生成树;用于连通所有点的最小代价网络。
概念解释
- 生成树:全顶点无环。
- MST:权值和最小。
- 边数 V-1。
原理流程
- 图连通。
- 选 V-1 条不成环边。
- 权值和最小。
代码 / 图示
V 点 → V-1 边 → 连通无环
常见误区
- 误区:MST 含环;正解:树无环。
- 误区:不连通图也有 MST;正解:需图连通,否则生成森林。
追问
- Q:MST 唯一吗? A:边权相等时可能多棵。
- Q:MST 边数? A:V-1。
02.4.2.4-010 Kruskal 算法怎么做?
一句话结论
边按权升序排序;逐条取边,两端不在同集合则加入 MST 并 union;已加入 V-1 条停止;并查集判环;O(E log E) 时间 O(E+V) 空间。
概念解释
- 贪心选最小边。
- DSU 防环。
- 边数 V-1。
原理流程
- 边排序。
- 逐条判同集。
- 不同集合并计入。
代码 / 示例
int kruskal(int n, int[][] edges) {
Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));
DSU dsu = new DSU(n);
int sum = 0, used = 0;
for (int[] e : edges) {
if (dsu.union(e[0], e[1])) {
sum += e[2];
if (++used == n - 1) break;
}
}
return used == n - 1 ? sum : -1; // 不连通返回 -1
}
常见误区
- 误区:成环边也加入;正解:同集跳过。
- 误区:不连通仍返回总和;正解:边数不足 V-1 判不连通。
追问
- Q:Kruskal 适合稀疏还是稠密? A:稀疏图友好,排序主导。
- Q:边权相等选哪条? A:任意,MST 权和相同。
02.4.2.4-011 Prim 算法怎么做?
一句话结论
从任意顶点出发维护已选集合;每次选连接集合内外的最小横切边加入,并入新顶点;堆维护候选边;O((V+E) log V),稠密图数组版 O(V²)。
概念解释
- 横切边:跨集合内外。
- 贪心最小。
- 逐步扩展树。
原理流程
- 起点入集。
- 选最小横切边。
- 并入顶点更新候选。
代码 / 示例
// 堆存 (权, 顶点),dist[v] 为连接已选集合的最小边权
常见误区
- 误区:Prim 按全局边排序;正解:按横切边选最小。
- 误区:已选顶点候选边重复处理;正解:标记已并入。
追问
- Q:Prim 与 Dijkstra 区别? A:Prim 记连接树的最小边权,Dijkstra 记起点距离。
- Q:稠密图 Prim? A:数组版 O(V²) 更优。
02.4.2.4-012 Kruskal 与 Prim 怎么选?
一句话结论
稀疏图 Kruskal(排序 + DSU)实现简单;稠密图 Prim 数组版 O(V²) 免排序;两者均贪心正确;Kruskal 按边排序,Prim 按顶点扩展。
概念解释
- 边密度。
- 实现成本。
- 贪心等价。
原理流程
- 估算 E 与 V²。
- 稀疏选 Kruskal。
- 稠密选 Prim。
代码 / 图示
稀疏 E≈V:Kruskal O(E log E)
稠密 E≈V²:Prim O(V²)
常见误区
- 误区:Kruskal 用 DSU 判环;Prim 不用;正解:Prim 靠集合标记防环。
- 误区:两算法结果权和不同;正解:同为 MST,权和一致。
追问
- Q:加权有向图 MST? A:生成树概念面向无向。
- Q:最小生成森林? A:不连通图各分量分别生成。
02.4.2.4-013 负权、负环怎么识别与处理?
一句话结论
负权边 Bellman-Ford 可处理;负环上路径代价可无限降低,最短路不存在;Bellman-Ford 第 V 轮仍能更新即检测到负环;题目需先判断可达性。
概念解释
- 负权:单条边为负。
- 负环:环权和为负。
- 检测:额外松弛轮。
原理流程
- V-1 轮松弛。
- 第 V 轮检测更新。
- 有更新报负环。
代码 / 图示
更新持续到第 V 轮 → 负环
常见误区
- 误区:负权图用 Dijkstra;正解:换 Bellman-Ford。
- 误区:负环仍输出距离;正解:无最短路,报告无解。
追问
- Q:不可达负环影响吗? A:只影响可达负环的路径。
- Q:最小生成树有负权边吗? A:无向 MST 可含负权边,贪心仍成立。
02.4.2.4-014 网络延迟时间(LC 743)怎么做?
一句话结论
信号从 K 出发到各节点的最短时间;建加权有向图跑 Dijkstra;取最大距离为全网最晚到达;存在不可达返回 -1;O((V+E) log V)。
概念解释
- 单源最短路。
- 最晚到达 = 最大距离。
- 不可达判定。
原理流程
- 建邻接表带权。
- Dijkstra 求 K 到各点。
- 最大距离,不可达判 -1。
代码 / 示例
public int networkDelayTime(int[][] times, int n, int k) {
List<int[]>[] g = new List[n + 1];
for (int i = 1; i <= n; i++) g[i] = new ArrayList<>();
for (int[] t : times) g[t[0]].add(new int[]{t[1], t[2]});
int[] dist = dijkstra(k, g, n);
int max = 0;
for (int i = 1; i <= n; i++) {
if (dist[i] == Integer.MAX_VALUE) return -1;
max = Math.max(max, dist[i]);
}
return max;
}
常见误区
- 误区:取平均距离;正解:全员到达取最大。
- 误区:编号 0 起开数组漏 1;正解:按题目编号开 n+1。
追问
- Q:负权边版本? A:Bellman-Ford。
- Q:多源延迟? A:多源同时入队 Dijkstra 变体。
02.4.2.4-015 DAG 上最短路怎么做?
一句话结论
先拓扑排序,按拓扑序逐个松弛邻接边;前置处理完再更新后继;O(V+E),支持负权;最长路径同理改松弛方向。
概念解释
- 拓扑序保证前置完成。
- 顺序松弛。
- 负权安全。
原理流程
- 拓扑排序。
- 按序遍历顶点。
- 松弛后继。
代码 / 示例
for (int u : topo) {
for (int[] e : g[u]) {
dist[e[0]] = Math.min(dist[e[0]], dist[u] + e[1]);
}
}
常见误区
- 误区:DAG 也用 Dijkstra;正解:拓扑序 DP 更省且支持负权。
- 误区:拓扑序反了;正解:前置在前。
追问
- Q:DAG 最长路径? A:
max松弛,可求关键路径。 - Q:DAG 有环吗? A:定义无环。
02.4.2.4-016 最短路怎么回溯完整路径?
一句话结论
松弛更新时记录前驱节点 prev[v]=u;终点沿 prev 回溯到起点再反转;距离数组只存长度,前驱表存路径;多路径任选其一。
概念解释
- 前驱记录。
- 回溯反转。
- 距离与路径分离。
原理流程
- 更优距离时记 prev。
- 终点沿 prev 走。
- 反转得正向路径。
代码 / 示例
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
prev[v] = u;
}
常见误区
- 误区:只存距离无法回溯;正解:需前驱表。
- 误区:回溯方向未反转;正解:终点到起点需反转。
追问
- Q:多条最短路求字典序? A:松弛时比较路径口径。
- Q:BFS 路径回溯? A:同样记父节点。
02.4.2.4-017 最短路径与生成树题有哪些边界用例?
一句话结论
单点、无边、不可达、自环、平行边、负权/负环、不连通图、起点即终点;判空、不可达返回约定值与负环检测。
概念解释
- 空与最短。
- 不可达。
- 特殊权值。
原理流程
- 单点距离 0。
- 不可达保留 INF。
- 负环单独检测。
代码 / 图示
n=1 / 无边
不可达 → INF
平行边取最小权
常见误区
- 误区:不可达返回 0;正解:按题意返回 -1/INF。
- 误区:平行边只取一条;正解:保留最小权或全部松弛。
追问
- Q:自环影响最短路? A:非负自环不选。
- Q:不连通 MST? A:生成森林,边数不足 V-1。
02.4.2.4-018 最短路算法复杂度怎么汇报?
一句话结论
BFS O(V+E);Dijkstra 堆 O((V+E) log V)、数组 O(V²);Bellman-Ford O(VE);Floyd O(V³);存图邻接表 O(V+E),距离/前驱 O(V) 或 O(V²)。
概念解释
- 算法分档。
- 存图空间。
- 辅助结构。
原理流程
- 按权值与起点选算法。
- 标注时间阶。
- 分列存图与辅助空间。
代码 / 图示
BFS:O(V+E)
Dijkstra 堆:O((V+E) log V)
Bellman-Ford:O(VE)
Floyd:O(V³)
常见误区
- 误区:Dijkstra O(V+E);正解:堆取最小带 log。
- 误区:Floyd 空间 O(V);正解:距离矩阵 O(V²)。
追问
- Q:稠密图 Dijkstra 选数组版? A:O(V²) 免堆。
- Q:大规模全源? A:逐点 Dijkstra,稀疏时优于 Floyd。
02.4.2.4-019 最短路与 MST 常见误区有哪些?
一句话结论
负权误用 Dijkstra、堆过期条目不跳过、Floyd 循环顺序错、Kruskal 成环边计入、Prim 与 Dijkstra 概念混淆、不可达未判定;按算法前提逐条复核。
概念解释
- 前提条件。
- 状态维护。
- 判环/判不可达。
原理流程
- 复核权值条件。
- 检查过期与前驱。
- 判定连通性。
代码 / 图示
非负 → Dijkstra
负权 → Bellman-Ford
MST:DSU / 集合标记
常见误区
- 误区:把 MST 边权和当最短路;正解:两者目标不同。
- 误区:Dijkstra 距离可被后续负权刷新;正解:前提非负。
追问
- Q:MST 上两点路径是最短路吗? A:不一定。
- Q:最短路径树是什么? A:从起点最短路前驱构成的树。
02.4.2.4-020 本知识域常见变体有哪些?
一句话结论
网络延迟、救援最短时间、网格最短路、航班中转、MST 最小代价连接、最小费用网络;主线是权值条件选最短路算法,连通代价选 MST 算法。
概念解释
- 单源/全源。
- 连通代价。
- 场景包装。
原理流程
- 判断点对距离还是全网连通。
- 判断权值正负。
- 选算法实现。
代码 / 图示
点对距离:最短路
全网连接:MST
网格:BFS / Dijkstra
常见误区
- 误区:网络连通问题误用最短路;正解:MST 求最小总代价。
- 误区:带权网格用 BFS;正解:权值不等用 Dijkstra。
追问
- Q:最小费用最大流? A:进阶网络流,超出本知识域。
- Q:两点间多条最短路? A:前驱表可扩展计数。