所有代码详见：https://github.com/jingminglake/Leetcode

总体思路

最短路径问题

N表示节点数量，E表示边的数量。

1. 单源最短路径，且没有负权边 使用Dijkstra。 普通情况下，时间复杂度O(N^2)。 如果图的边数较少，那么使用Dijkstra堆优化版本。时间复杂度O(ElogE) 一般来说，边不算多，直接使用堆优化版。

2. 单源最短路径，有负权边，但没有负权回路 使用Bellman-Ford。时间复杂度O(N * E)。

如果图的边数比较少，那么使用BellmanFord的队列优化版本SPFA。时间复杂度O（K * N）。一般来说，K比E小。

订正（2026-10-07）：SPFA 的最坏复杂度和 Bellman-Ford 一样是 O(N·E)，「一般比 E 小」只是平均情况，而且容易被特意构造的数据卡掉，面试一般不推荐。

1. 多源最短路径 使用Floyd。时间复杂度O(N^3)。

2. 点到点最短路径 使用BFS。再BFS的基础上，进行A star。A star的时间复杂度不确定，最坏情况下，A * 退化成BFS，时间复杂度O(N^2)，

最好情况下，是从起点直接到终点，时间复杂度为 O(dlogd)，d 为起点到终点的深度。

订正（2026-10-07）：BFS 求最短路只适用于无权图（或所有边权相等），有权图即使是点到点也要用 Dijkstra。A* 面试基本不考，上面「最好 O(dlogd)」的说法没有实际意义，了解即可。

一、图算法地图：看到什么信号，用什么算法（2026-10-07）

二、Dijkstra 的不变量

不变量：从堆里弹出的、还没确定过的点中距离最小的那个，它的距离已经是最终答案。

理由：设 u 是当前最小的未确定点，距离 d。任何更短的路都要先经过某个未确定点 x，到 x 已花了 ≥ d，之后边权 ≥ 0，整条路不可能比 d 短。

为什么不能有负边：上面最后一步依赖「之后的边权 ≥ 0」。反例：k→A 权 1，k→B 权 5，B→A 权 -10。Dijkstra 先弹出 A（距离 1）并确定，但 k→B→A 才是 -5。

推广：真正需要的是「路径代价沿路不减」。边权和（非负边）满足，路上最大值（778）也满足，所以 778 只需把更新式的 d + w 换成 max(d, h)。

懒删除：Java 的 PriorityQueue 不支持修改优先级（无 decrease-key），所以更新距离时直接再压一条新记录，旧记录留着；弹出时 d > dist[u] 就是过期记录，跳过。

为什么是 > 不是 >=：每条记录压入时 d 就等于当时的 dist[v]（是前驱更新 dist[v] 时一起写入的），之后 dist[v] 只会变小。所以出堆时 d == dist[u] 说明这就是最新的那条，要处理；d > dist[u] 说明后来又被改小过，是过期记录。写成 >= 连起点 (0, k) 都会被跳过。（等价写法：boolean[] done，第一次弹出才处理。）

数组版 O(N²) 还是堆版 O(ElogE)：看稠密还是稀疏。每轮「找最小点」数组版要扫 N 个点，堆版 O(logE)。稀疏图（E 与 N 同量级）堆版远好；稠密图（E 接近 N²，如邻接矩阵输入、平面上任意两点可连）堆版反而是 O(N²logN)，数组版更好。面试默认堆版，看到稠密信号再换数组版并说出理由。

三、Bellman-Ford：有没有步数限制，决定能不能原地更新

状态：第 i 轮结束后，dist[v] = 最多用 i 条边从起点到 v 的最短距离。每轮用每条边 u→v 松弛一次。

• 纯版本：跑 N-1 轮（无负环时最短路最多 N-1 条边）。可以原地更新——同一轮里接力走多条边只会让结果提前收敛，每个值都对应一条真实路径，不会出错。
• 判负环：N-1 轮后再扫一遍，还能变小就说明有负环。货币套利：边权取 -log(rate)，一圈汇率乘积 > 1 等价于边权和 < 0，即负环。
• 限制最多 K 条边（787）：只跑 K 轮，必须从 prev 读、往 cur 写。原地更新会在同一轮里接力，一轮走多条边，偷偷突破限制。和股票系列坚持 prev/cur 是同一个原则：这一轮只能用上一轮的状态。

四、最小生成树

切分性质：把点任意分成两堆，横跨两堆最便宜的边一定可以出现在某棵最小生成树里。（若某棵 MST 不含它，加进去成环，环上必有另一条横跨两堆的边，删掉那条，总费用不增。）

• Kruskal：边按费用排序，两端不连通就选（并查集判断），选够 N-1 条就停。N 个点各自一块，每选一条边合并两块，合成一块恰好要 N-1 次。适合直接给出边集的题。
• Prim：从一点长树，minCost[v] = 把 v 接到当前树上的最便宜边；每轮把 minCost 最小的树外点加进来，再用它更新其他树外点。数组版 O(N²)，稠密图最优。

Prim 和 Dijkstra 只差一个式子：

Dijkstra 关心整条路径所以要加上 dist[u]；Prim 只关心这一条边接上树的代价。

五、散落在其他篇的图题

• 《总结（五）》BFS：200、133、286、417、207、210、127、269、310
• 《总结（六）》DFS：332、785、399、802
• 《总结（九）》并查集：684、261、721、128

待补（NeetCode 对照）：695、130、994、323。

题目

743. Network Delay Time

题意：n 个节点（编号 1..n），有向带权边 times[i] = [u, v, w]。从 k 发出信号，求所有节点都收到信号的最短时间；有节点收不到返回 -1。

解：每个节点最早收到信号的时间就是 k 到它的最短路，所有节点都收到的时刻是其中最大的。所以答案 = max(dist[1..n])，有无穷大就返回 -1。非负边权，单源最短路，用 Dijkstra 堆优化版。

骨架三步：弹出最小 → 过期就跳过（d > dist[u]）→ 松弛邻居、压入新记录。不变量与懒删除见上文第二节。

注意：

（1）松弛写 d + w < dist[v]，用弹出的 d 而不是 dist[u]，dist[v] 可能是 MAX_VALUE 但只出现在比较右边，不会溢出。

（2）邻接表用 List<List<int[]>>，先 add 满 n+1 个空 list（Java 的 ArrayList 没有空位，get 越界抛异常）；编号从 1 开始，下标 0 空着。也可以用 List<int[]>[]（泛型数组，要逐格 new），或 n ≤ 100 时直接用邻接矩阵（用 -1 表示无边，因为 0 可能是合法边权）。

（3）本题 n ≤ 100、边 ≤ 6000，数组版 10⁴ 次比堆版还少，但面试默认写堆版。也可以用纯 Bellman-Ford（N-1 轮、原地更新）再做一遍来练手。

787. Cheapest Flights Within K Stops

题意：n 个城市，航班 [from, to, price]，从 src 到 dst 最多经停 K 站，求最低票价，到不了返回 -1。

解：经停的是点，坐的是边：经停 K 站 = 最多 K+1 段航班（K=0 就是直飞 1 条边）。

为什么 Dijkstra 会错：例 0→1(1)、1→2(1)、2→3(1)、0→2(5)，K=1。正确答案 0→2→3 = 6。Dijkstra 先用便宜的 0→1→2（花 2、用了 2 条边）确定了 2，之后 0→2（花 5、1 条边）被当成过期记录跳过，可从 2 再飞到 3 就超限了，结果 -1。根因：多了「已用边数」这个维度，便宜但边多的路和贵但边少的路谁也不比谁好，只记最低价信息不够——和 403 青蛙过河「状态必须带上上一跳长度」是同一个问题。

Bellman-Ford 跑 K+1 轮：prev[v] = 最多用 i 条边到 v 的最低价。每轮 cur = prev.clone()（用更少的边能到，多给一条边当然也能到），对每条航班 u→v：prev[u] 不是无穷大时 cur[v] = min(cur[v], prev[u] + w)。O(K·E)。

为什么必须 prev（面试一句话）：第 i 轮的含义是「最多 i 条边」，原地更新时同一轮里刚更新的值会被后面的边接着用，一轮就可能走好几条边。例：链 0→1→2、K=0，先处理 0→1 更新了 dist[1]，再处理 1→2 时原地写法读到它，dist[2] 也有了值，可 0 到 2 根本没有直飞。上例原地更新会得到 3（0→1→2→3，3 条边）。补一句：纯 Bellman-Ford 没有边数限制，就不需要 prev。

另一种写法：状态扩成 (点, 已用边数) 再跑 Dijkstra，可行但剪枝容易写错，面试推荐 Bellman-Ford。

识别信号：路径上有步数／站数／次数限制，先想「按步数一轮轮推进」。

1584. Min Cost to Connect All Points

题意：平面上 n 个点 points[i] = [x, y]，连接两点的费用是曼哈顿距离 |x1-x2| + |y1-y2|，求连通所有点的最小总费用。

解：任意两点都有边（费用用坐标算出来，共 n(n-1)/2 条），求最小生成树。注意 n 是点数不是边数。

方法一：Kruskal。生成所有边并按费用排序，用并查集依次选不成环的边，选够 n-1 条提前结束。O(n²logn)。if (++used == n - 1) break 建议拆成两行（used++; if (used == n - 1) break;），压成一行要想清楚 ++used 是先加后比；used++ == 会多选一条才停。

方法二：Prim 数组版。minCost[0] = 0 开始长树，每轮选树外 minCost 最小的点加入、累加费用，再用它更新其他树外点。O(n²)，空间 O(n)，不用存边。这是一张稠密图，Prim 数组版是最优解，堆版反而 O(n²logn)。

778. Swim in Rising Water

题意：n×n 网格，grid[i][j] 是高度（0 到 n²-1 的排列）。时刻 t 水深 t，高度 ≤ t 的格子被淹没，可以在相邻的被淹没格子间瞬间游动。求最早什么时刻能从左上游到右下。

解：一条路能走通要等路上最高的格子被淹没，所以答案 = 所有路径中「路上最大高度」的最小值（minimax／瓶颈路径）。

方法一：改版 Dijkstra。dist = 到该格所有路径中路上最大高度的最小值，起点 dist = grid[0][0]（起点本身也要被淹没），更新式把 d + w 换成 max(d, grid[nr][nc])。max 沿路不减，不变量成立。终点出堆即可返回（743 要等所有点确定，是因为它要所有点的最大值）。O(n²logn)。

方法二：二分答案 + BFS。谓词「时刻 T 能否到达」单调（T 能到则 T+1 也能），在 [grid[0][0], n²-1] 上找第一个 true，每次检查只走高度 ≤ T 的格子做 BFS。O(n²logn)。识别信号：「最小的 X 使得某事可以做到，且 X 越大越容易」。

方法三：按高度加格子 + 并查集。时刻 t 把高度为 t 的格子（高度是排列，用 pos[h] 直接找到，不用排序）与已淹没的邻居 union，起点和终点第一次连通的时刻就是答案。二维坐标压成 r * n + c 给并查集用。这就是 1584 Kruskal 的想法：按代价从小到大加入，一连通就停。

面试推荐方法一：改动最小，还能顺势讲出「代价沿路不减就能用 Dijkstra」。

• 上一篇
  Leetcode按题目类型总结（二十）
• 下一篇
  Leetcode按题目类型总结（二十一）