专题 22图论进阶：最短路与最小生成树

22.1带权图与最短路的两大家族

先建立一张「选择地图」，避免拿到题不知道掏哪个算法。带权最短路主要分三派：

为什么带权后 BFS 不行了

专题 12 里 BFS 的「层数 = 距离」成立，前提是每条边代价相等（都是 1）。一旦边权不同，走 3 条边未必比走 1 条边远——「先到的不一定更近」。所以必须引入能比较「真实累积代价」的算法，这就是 Dijkstra 和 Bellman-Ford 的出发点。

邻接表怎么建

带权图几乎都用邻接表存：每个节点挂一串「邻居 + 边权」。Java 里最顺手的是 List，其中 int[]{to, weight} 表示「到 to 的边、权重 weight」：

int n = ...;                              // 节点数
List<int[]>[] graph = new List[n];        // 邻接表
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
// 加一条有向边 u -> v，权重 w
graph[u].add(new int[]{v, w});

22.2网络延迟时间：Dijkstra（中等，力扣 743）

中等 核心：小顶堆 · 惰性删除

题意：有 n 个节点（编号 1~n），times[i] = [u, v, w] 表示信号从 u 到 v 需要 w 毫秒（有向）。从节点 k 发出信号，求所有节点都收到信号的最短时间（即「最远的那个节点」收到的时间）；若有节点收不到，返回 -1。 例：n=4, k=2, times=[[2,1,1],[2,3,1],[3,4,1]] → 节点 4 最后收到，耗时 2，返回 2。

思路推导

第一步，这本质就是单源最短路。从 k 出发到每个点的最短时间就是「k 到该点的最短路」。因为边权都是正毫秒（非负），用 Dijkstra。

第二步，Dijkstra 的核心直觉——「贪心确定最近点」。维护每个点的「当前已知最短距离」dist[]，初始除 k 外都是无穷大。用一个小顶堆（优先队列）存 (距离, 节点)，始终弹出「当前距离最小」的点。

关键性质：从堆里 poll 出来的一个点，它此时的距离就是最终最短距离——因为所有还没确定的点距离都更大，不可能再找到一条更短的路绕过它。第一次弹出即确定，这就是 Dijkstra 的正确性基石。

第三步，「惰性删除」为什么安全。一个节点可能被多次入队（每次通过不同邻居松弛出更小的距离）。但我们用一个 visited（或对比 dist）判断：一旦某点已被确定（弹出的距离 ≤ 已知 dist），再遇到它就直接跳过。旧的大距离记录「躺在堆里不用管」，相当于惰性删除，省去手动维护堆的麻烦。

第四步，答案是「最远节点」。所有点都确定后，dist 数组里的最大值就是「最后一个收到信号的时间」。若有任何 dist 仍是无穷大，说明有节点不可达，返回 -1。

参考代码

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        // 建邻接表：graph[u] 存 {v, w}
        List<int[]>[] graph = new List[n + 1];
        for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();
        for (int[] t : times) graph[t[0]].add(new int[]{t[1], t[2]});

        int[] dist = new int[n + 1];                 // 最短距离
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;
        // 小顶堆：(距离, 节点)，按距离升序
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, k});

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int d = cur[0], u = cur[1];
            if (d > dist[u]) continue;               // 惰性删除：旧记录跳过
            for (int[] edge : graph[u]) {             // 松弛邻居
                int v = edge[0], w = edge[1];
                if (dist[u] + w < dist[v]) {          // 找到更近的路
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{dist[v], v});  // 入队（可能重复，靠上面跳过）
                }
            }
        }

        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1; // 有节点不可达
            ans = Math.max(ans, dist[i]);                 // 取最远
        }
        return ans;
    }
}

复杂度

O((V+E) log V) 时间（每个点/边最多入堆一次，堆操作 log V），O(V+E) 空间（邻接表 + 堆 + dist）。边权非负时这是最优单源最短路。

22.3K 站中转内最便宜的航班：Bellman-Ford（中等，力扣 787）

中等 核心：限步松弛 · 备份数组

题意：有 n 个城市，flights[i] = [u, v, w] 表示从 u 到 v 的票价 w。求从 src 到 dst、最多经 K 站中转（即最多坐 K+1 段航班）的最低价格；无法到达返回 -1。 例：n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, k=1 → 经 1 站走 0→1→2 共 200，比直飞 500 便宜，返回 200。

思路推导

第一步，为什么这里 Dijkstra 不合适。本题多了一个硬约束：「最多中转 K 次」。Dijkstra 按距离贪心，可能先选一条「步数多但总价低」的路，而它超过了 K 步限制；或者相反，一条「步数少但贵」的路才是合法的。Dijkstra 本身不区分「走了几步」，硬塞步数维度会把状态搞复杂。限制步数（或处理负权）正是 Bellman-Ford 的强项。

第二步，Bellman-Ford 的本质——「按轮松弛」。标准 Bellman-Ford 做 |V|-1 轮，每轮遍历所有边，尝试用 u→v 把 dist[v] 缩短（松弛）。经过 t 轮松弛后，dist 里装的就是「最多走 t 条边」能到达的最短路——轮数天然对应步数。

第三步，关键的「备份数组」技巧。最容易写错的地方：如果直接在原 dist 上松弛，同一轮里前面更新的结果会被后面「串联」利用，导致一轮就走了多步，破坏了「第 t 轮恰好 t 步」的语义。解决办法：每轮开始前把上一轮的 dist 备份成 prev，这一轮所有松弛都基于 prev 去更新新 dist：

for (每一轮 t = 1 .. K+1):          // K+1 条边 = K 站中转
    prev = dist 的副本
    for (每条边 u->v 票价 w):
        if (prev[u] != INF)
            dist[v] = min(dist[v], prev[u] + w)   // 必须用上一轮的 prev[u]!

这样每一轮严格只「多走一条边」,走满 K+1 条边即满足「最多 K 站中转」。

参考代码

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int INF = Integer.MAX_VALUE / 2;
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[src] = 0;

        // 最多 K 站中转 = 最多坐 K+1 段航班 = 松弛 K+1 轮
        for (int t = 1; t <= k + 1; t++) {
            int[] prev = dist.clone();          // 备份上一轮（关键！）
            for (int[] f : flights) {
                int u = f[0], v = f[1], w = f[2];
                if (prev[u] != INF) {            // 基于 prev 松弛，避免一轮串联
                    dist[v] = Math.min(dist[v], prev[u] + w);
                }
            }
        }
        return dist[dst] == INF ? -1 : dist[dst];
    }
}

复杂度

O(K·E) 时间（K+1 轮 × 边数 E），O(V) 空间。当 K 较小而图大时，比跑完整 |V|-1 轮的标准 Bellman-Ford 更快，也比重载 Dijkstra 干净。

22.4Floyd：多源最短路

核心：dp 三重循环 · 经 k 会不会更近

它解决什么：前面 Dijkstra / Bellman-Ford 都是单源（从一个点出发）。如果题目要你回答「任意两个点之间的最短距离」（比如「从每个城市到其他所有城市各要多久」），对每个点都跑一遍 Dijkstra 是 O(V·(V+E)logV)。当 V 很小（≤200）时，Floyd 用一段极短的代码一次性算完所有点对，更香。

思路推导

核心想法：设 dp[i][j] 是 i 到 j 的当前最短距离。我们允许路径经过编号为 1…k 的点当中转。那么「允许经过 k」相比「只经过 1…k-1」,唯一可能变短的情况是：绕道走 i→k→j 比原来的 i→j 更近。于是得到著名的转移：

dp[i][j] = min( dp[i][j], dp[i][k] + dp[k][j] )

外层枚举 k（中转点），内层两重枚举 i, j。注意 k 必须在最外层——它代表「逐步放开可经的中转集合」，内层 i,j 顺序无所谓。三个循环都是 0..n-1，构成 O(n³)。

参考代码（短小精悍）

// 初始化：dp[i][i]=0；有直接边 dp[i][j]=w；其余 INF
for (int k = 0; k < n; k++) {            // 中转点，必须在最外层
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dp[i][k] < INF && dp[k][j] < INF) {
                dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
            }
        }
    }
}

复杂度

O(n³) 时间，O(n²) 空间。只适合点数小的图（n≤200 左右）。它还能顺便判传递闭包（可达性）、做除法求值等，见下方巩固练习。

22.5连接所有点的最小费用：Kruskal（中等，力扣 1584）

中等 核心：边排序 + 并查集判环

题意：平面上有 n 个点，连接点 i 和 j 的代价是它们的曼哈顿距离。求把这些点全部连通（任意两点间有路径）的最小总代价。 例：points = [[0,0],[2,2],[3,10],[5,2],[7,0]] → 最小生成树总代价为 20。

思路推导

第一步，问题转化 = 最小生成树（MST）。「连通所有点 + 总权最小 + 无环」正是 MST 的定义。任意两点都能连（完全图），我们要挑 n-1 条边把 n 个点连成一棵树，且总权最小。

第二步，为什么 Kruskal 直观。贪心思路：能连就尽量连便宜的边。把所有「候选边」按权值从小到大排序，依次考虑：若这条边连接的两个点当前还不连通，就选它（加入生成树）；若已经连通（加了会成环），就跳过。选够 n-1 条即停。

第三步，「判环」靠并查集（承接 专题 20）。判断两点是否连通，就是查它们是否同属一个集合——这正是并查集的拿手好戏。选边时 find(u) != find(v) 说明不连通，union 合并；相等则跳过。这样保证最后是一棵无环的树。

第四步，对比 Prim（一句话）。Prim 是「从某个点出发，每次把离已连通集合最近的未连通点拉进来」，用堆维护。Kruskal 是「全局按边排序 + 并查集」。两者都得到 MST，边多（稠密图）用 Prim，边少或想写简单用 Kruskal。

参考代码

class Solution {
    int[] parent;
    int find(int x) {                       // 并查集找根 + 路径压缩
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void union(int a, int b) { parent[find(a)] = find(b); }

    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;

        // ① 生成所有边 (u, v, 曼哈顿距离)
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                int d = Math.abs(points[i][0] - points[j][0])
                      + Math.abs(points[i][1] - points[j][1]);
                edges.add(new int[]{d, i, j});
            }
        // ② 按权值排序（Kruskal 核心：贪心选最小边）
        edges.sort((a, b) -> a[0] - b[0]);

        int ans = 0, cnt = 0;               // cnt 记录已选边数
        for (int[] e : edges) {
            int d = e[0], u = e[1], v = e[2];
            if (find(u) != find(v)) {       // 不连通才选，避免成环
                union(u, v);
                ans += d;
                cnt++;
                if (cnt == n - 1) break;    // 选够 n-1 条边即连通，停
            }
        }
        return ans;
    }
}

复杂度

建边 O(n²)、排序 O(n² log n²)、并查集近乎 O(1)，总 O(n² log n) 时间，O(n²) 空间（边集）。这是 MST 的标准模板，可直接套用到任何「连点最小代价」题。

22.6本专题常见坑

22.7自测题