罗罗编程学习记录
本页内容 展开查看

02.4.2.4 最短路径与最小生成树

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.4 树与图 / 02.4.2 图论与并查集

02.4.2.4-001 最短路径问题分哪几类?

一句话结论

按需求分:无权图最短路(BFS)、单源最短路(Dijkstra/Bellman-Ford)、全源最短路(Floyd);按权值分非负权与含负权;按图型分一般图与 DAG。

概念解释

  • 单源:一个起点到各点。
  • 全源:所有点对。
  • 权值:是否允许负边。

原理流程

  1. 明确起点数量。
  2. 判断边权正负。
  3. 选算法。

代码 / 图示

无权 → 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) 队列。

概念解释

  • 边代价相同。
  • 层序 = 距离。
  • 首达最短。

原理流程

  1. 起点距离 0 入队。
  2. 逐层扩展。
  3. 未访问记录距离。

代码 / 示例

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) 堆实现。

概念解释

  • 已确定集合。
  • 贪心取最小距离。
  • 松弛后继。

原理流程

  1. 起点距离 0,其余无穷。
  2. 取未确定最小距离点。
  3. 松弛邻接,更新距离。

代码 / 图示

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) 堆。

概念解释

  • 堆:取最小距离。
  • 惰性删除:过期条目跳过。
  • 邻接松弛。

原理流程

  1. 距离数组初始化。
  2. 堆起点入队。
  3. 弹出、跳过旧条目、松弛。

代码 / 示例

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;存在负环无最短路。

概念解释

  • 贪心前提。
  • 负权反例。
  • 算法边界。

原理流程

  1. 非负:已选点距离已定。
  2. 负权:后到路径可能更短。
  3. 贪心失效。

代码 / 图示

选定点 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) 堆/距离。

概念解释

  • 堆操作对数。
  • 边触发更新。
  • 稠密取舍。

原理流程

  1. 统计边数。
  2. 堆操作次数 ≤ E。
  3. 标注存图与堆空间。

代码 / 图示

堆: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 轮收敛。
  • 负环检测。

原理流程

  1. 距离初始化。
  2. 重复 V-1 轮松弛全部边。
  3. 再松弛一轮判负环。

代码 / 示例

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²) 空间,支持负权(无负环)。

概念解释

  • 全源:点对距离。
  • 中间点枚举。
  • 动态规划。

原理流程

  1. 矩阵初始化直连边权。
  2. 枚举中间点松弛。
  3. 结果矩阵即全源距离。

代码 / 示例

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。

原理流程

  1. 图连通。
  2. 选 V-1 条不成环边。
  3. 权值和最小。

代码 / 图示

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。

原理流程

  1. 边排序。
  2. 逐条判同集。
  3. 不同集合并计入。

代码 / 示例

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²)。

概念解释

  • 横切边:跨集合内外。
  • 贪心最小。
  • 逐步扩展树。

原理流程

  1. 起点入集。
  2. 选最小横切边。
  3. 并入顶点更新候选。

代码 / 示例

// 堆存 (权, 顶点),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 按顶点扩展。

概念解释

  • 边密度。
  • 实现成本。
  • 贪心等价。

原理流程

  1. 估算 E 与 V²。
  2. 稀疏选 Kruskal。
  3. 稠密选 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 轮仍能更新即检测到负环;题目需先判断可达性。

概念解释

  • 负权:单条边为负。
  • 负环:环权和为负。
  • 检测:额外松弛轮。

原理流程

  1. V-1 轮松弛。
  2. 第 V 轮检测更新。
  3. 有更新报负环。

代码 / 图示

更新持续到第 V 轮 → 负环

常见误区

  • 误区:负权图用 Dijkstra;正解:换 Bellman-Ford。
  • 误区:负环仍输出距离;正解:无最短路,报告无解。

追问

  • Q:不可达负环影响吗? A:只影响可达负环的路径。
  • Q:最小生成树有负权边吗? A:无向 MST 可含负权边,贪心仍成立。

02.4.2.4-014 网络延迟时间(LC 743)怎么做?

一句话结论

信号从 K 出发到各节点的最短时间;建加权有向图跑 Dijkstra;取最大距离为全网最晚到达;存在不可达返回 -1;O((V+E) log V)。

概念解释

  • 单源最短路。
  • 最晚到达 = 最大距离。
  • 不可达判定。

原理流程

  1. 建邻接表带权。
  2. Dijkstra 求 K 到各点。
  3. 最大距离,不可达判 -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),支持负权;最长路径同理改松弛方向。

概念解释

  • 拓扑序保证前置完成。
  • 顺序松弛。
  • 负权安全。

原理流程

  1. 拓扑排序。
  2. 按序遍历顶点。
  3. 松弛后继。

代码 / 示例

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 回溯到起点再反转;距离数组只存长度,前驱表存路径;多路径任选其一。

概念解释

  • 前驱记录。
  • 回溯反转。
  • 距离与路径分离。

原理流程

  1. 更优距离时记 prev。
  2. 终点沿 prev 走。
  3. 反转得正向路径。

代码 / 示例

if (dist[u] + w < dist[v]) {
    dist[v] = dist[u] + w;
    prev[v] = u;
}

常见误区

  • 误区:只存距离无法回溯;正解:需前驱表。
  • 误区:回溯方向未反转;正解:终点到起点需反转。

追问

  • Q:多条最短路求字典序? A:松弛时比较路径口径。
  • Q:BFS 路径回溯? A:同样记父节点。

02.4.2.4-017 最短路径与生成树题有哪些边界用例?

一句话结论

单点、无边、不可达、自环、平行边、负权/负环、不连通图、起点即终点;判空、不可达返回约定值与负环检测。

概念解释

  • 空与最短。
  • 不可达。
  • 特殊权值。

原理流程

  1. 单点距离 0。
  2. 不可达保留 INF。
  3. 负环单独检测。

代码 / 图示

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²)。

概念解释

  • 算法分档。
  • 存图空间。
  • 辅助结构。

原理流程

  1. 按权值与起点选算法。
  2. 标注时间阶。
  3. 分列存图与辅助空间。

代码 / 图示

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 概念混淆、不可达未判定;按算法前提逐条复核。

概念解释

  • 前提条件。
  • 状态维护。
  • 判环/判不可达。

原理流程

  1. 复核权值条件。
  2. 检查过期与前驱。
  3. 判定连通性。

代码 / 图示

非负 → Dijkstra
负权 → Bellman-Ford
MST:DSU / 集合标记

常见误区

  • 误区:把 MST 边权和当最短路;正解:两者目标不同。
  • 误区:Dijkstra 距离可被后续负权刷新;正解:前提非负。

追问

  • Q:MST 上两点路径是最短路吗? A:不一定。
  • Q:最短路径树是什么? A:从起点最短路前驱构成的树。

02.4.2.4-020 本知识域常见变体有哪些?

一句话结论

网络延迟、救援最短时间、网格最短路、航班中转、MST 最小代价连接、最小费用网络;主线是权值条件选最短路算法,连通代价选 MST 算法。

概念解释

  • 单源/全源。
  • 连通代价。
  • 场景包装。

原理流程

  1. 判断点对距离还是全网连通。
  2. 判断权值正负。
  3. 选算法实现。

代码 / 图示

点对距离:最短路
全网连接:MST
网格:BFS / Dijkstra

常见误区

  • 误区:网络连通问题误用最短路;正解:MST 求最小总代价。
  • 误区:带权网格用 BFS;正解:权值不等用 Dijkstra。

追问

  • Q:最小费用最大流? A:进阶网络流,超出本知识域。
  • Q:两点间多条最短路? A:前驱表可扩展计数。