图论 · 最短路
从 LC 743 出发，看 Dijkstra / Bellman-Ford / Floyd 各自适用的场景。
1. 核心原理
最短路问题给定一张图 G = (V, E) 与边权函数 w: E → ℝ，要求从源点 s 到其他节点（或所有点对）的最小累积边权。这是图论里最经典的"贪心 + 松弛"问题——边权的取值范围（是否非负、是否带负环）、问题规模（单源 vs 全源、V 与 E 的大小）决定了选哪种算法。
朴素枚举所有路径不可行：从 s 到任一节点的简单路径数随图的稠密程度呈指数级。最短路算法的核心 invariant 是松弛操作的单调性：对边 (u, v, w)，若 dist[u] + w < dist[v] 则把 dist[v] 更新为 dist[u] + w。所有最短路算法的差别仅在于"按什么顺序松弛 + 何时确认一个节点的距离已经最优"。
按边权特征选算法
不同的边权特征对应不同的算法：
- 边权全 1：用 BFS。按"层"扩张，每层
+1距离，复杂度O(V + E)。 - 边权 ∈ 1：用 0-1 BFS（双端队列：0 边推队首，1 边推队尾）。复杂度
O(V + E)。 - 边权非负实数：用 Dijkstra 算法 + 优先队列。复杂度
O((V + E) log V)。 - 含负权（但无负环）：用 Bellman-Ford 或 SPFA。复杂度
O(V × E)。也能检测负环。 - 全源最短路：用 Floyd-Warshall。三层循环、
O(V³)，V小（≤ 400）时舒适。
LeetCode 上的最短路题，绝大多数边权非负——Dijkstra 是默认选项。只有少数题（如 LC 787 限制中转次数）需要 Bellman-Ford；LC 1334 这种全源 + V 小的场景适合 Floyd。
Dijkstra 的正确性：第一次出堆即最短
Dijkstra 的核心断言是"边权非负时，节点 v 第一次从优先队列弹出时，dist[v] 就是最终最短距离"。反证：若真正最短距离 d' < d，则该最短路径上存在中间节点 u 在 v 之前出堆，且 dist[u] ≤ d'。u 出堆时会松弛 (u, v)，让 dist[v] 至少降到 dist[u] + w(u, v) ≤ d'，与"v 出堆时距离为 d > d'"矛盾。
这条性质只在非负权下成立。出现负边时，u 在 v 之后才出堆也可能让 dist[v] 进一步变小，Dijkstra 直接失效，必须换 Bellman-Ford。
Dijkstra 实现要点
主流实现是"松弛 + 出堆即定型 + 懒删除"：
dist[]初始化为+∞，dist[s] = 0，把(0, s)推进最小堆- 循环：弹堆顶
(d, u)；若d > dist[u]是过期记录，跳过；否则遍历u的出边(u, v, w)，能松弛就更新dist[v]并把(dist[v], v)推堆 - 堆空结束。每个节点最多被 push
O(E)次（每次松弛成功 push 一次），总堆操作O(E log V)，整体O((V + E) log V)。
"懒删除"那一行 if d > dist[u]: continue 是关键——Python heapq / Java PriorityQueue 不支持 decrease-key，所以堆里会留下若干个 (过期距离, u) 记录。遇到时直接跳过即可，结果正确，复杂度也正确。漏掉这一行算法仍然返回正确答案，但同一节点会被反复处理，最坏复杂度退化。
负权下 Dijkstra 失效的反例
0 → 1 (w=2), 0 → 2 (w=1), 2 → 1 (w=-3)。从 0 出发，Dijkstra 第一次弹出 1 时 dist[1] = 2，节点 1 被"定型"；但真实最短是 0 → 2 → 1 = -2。原因是"边权非负"前提下"第一次出堆即最短"的反证逻辑在负权下不成立——后出堆的节点可能进一步松弛已经出堆的节点。出现负权时必须换 Bellman-Ford。
三者关系速查
把单源最短路三件套放在同一张表对比：
| 维度 | Dijkstra | Bellman-Ford | Floyd |
|---|---|---|---|
| 起点 | 单源 | 单源 | 全源 |
| 负权 | 不支持 | 支持 | 支持（无负环） |
| 负环检测 | - | 跑第 V 轮看能否松弛 | 看 dist[i][i] < 0 |
| 边数限制 | - | 跑 k + 1 轮即可 | - |
| 时间复杂度 | O((V+E) log V) | O(V × E) | O(V³) |
| 何时选 | 大图非负权 | 小图含负权 / 边数限制 | 小图全源 |
Bellman-Ford 的"对每条边做 V - 1 轮松弛"——经过 V - 1 轮后，任何最短路径（最多 V - 1 条边）都被完整松弛过一次；第 V 轮再跑还能松弛就意味着存在负环。SPFA（Shortest Path Faster Algorithm）是它的队列优化版本：只对"上一轮被松弛过的节点"重新松弛邻居，平均更快但最坏仍是 O(V × E)。Floyd 的状态转移逻辑：dist[i][j] 在第 k 轮表示"只允许使用编号 < k 的中间节点时 i 到 j 的最短距离"，第 k 轮决定"要不要把 k 加进中间节点池"。
2. 通用模板
下面给三类主算法的最小骨架：Dijkstra 堆优化（最常用）、Bellman-Ford 带边数限制、Floyd 全源最短路。V、E 含义统一为节点数与边数；输入 edges 默认为 (u, v, w) 三元组列表，下标从 0 开始。
import heapq
from math import inf
def dijkstra(n: int, edges: list[tuple[int, int, int]], src: int) -> list[float]:
"""Dijkstra 堆优化：单源最短路，要求边权非负"""
g = [[] for _ in range(n)]
for u, v, w in edges:
g[u].append((v, w))
dist = [inf] * n
dist[src] = 0
pq = [(0, src)] # (距离, 节点)
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]: # 懒删除：过期记录跳过
continue
for v, w in g[u]:
nd = d + w
if nd < dist[v]: # 松弛成功才入堆
dist[v] = nd
heapq.heappush(pq, (nd, v))
return dist
def bellman_ford(n, edges, src, k):
"""带边数限制：最多走 k 条边时 src 到每点的最短距离"""
dist = [inf] * n
dist[src] = 0
for _ in range(k): # 跑 k 轮
prev = dist[:] # 用上一轮副本松弛
for u, v, w in edges:
if prev[u] + w < dist[v]:
dist[v] = prev[u] + w
return dist
def floyd(n, edges):
"""全源最短路：返回 n × n 距离矩阵"""
INF = float('inf')
dist = [[INF] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = min(dist[u][v], w) # 处理重边取小
for k in range(n): # k 是中间节点
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist// Dijkstra 堆优化：单源最短路，要求边权非负
static long[] dijkstra(int n, int[][] edges, int src) {
List<int[]>[] g = new List[n];
for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
for (int[] e : edges) g[e[0]].add(new int[]{e[1], e[2]});
long[] dist = new long[n];
Arrays.fill(dist, Long.MAX_VALUE);
dist[src] = 0;
PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
pq.offer(new long[]{0, src});
while (!pq.isEmpty()) {
long[] cur = pq.poll();
long d = cur[0];
int u = (int) cur[1];
if (d > dist[u]) continue; // 懒删除
for (int[] nb : g[u]) {
int v = nb[0], w = nb[1];
long nd = d + w;
if (nd < dist[v]) {
dist[v] = nd;
pq.offer(new long[]{nd, v});
}
}
}
return dist;
}
// Bellman-Ford 带边数限制
static int[] bellmanFordK(int n, int[][] edges, int src, int k) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
for (int i = 0; i < k; i++) {
int[] prev = dist.clone();
for (int[] e : edges) {
if (prev[e[0]] != Integer.MAX_VALUE
&& prev[e[0]] + e[2] < dist[e[1]]) {
dist[e[1]] = prev[e[0]] + e[2];
}
}
}
return dist;
}
// Floyd-Warshall：全源最短路，返回 n × n 距离矩阵
static int[][] floyd(int n, int[][] edges) {
int INF = Integer.MAX_VALUE / 2; // 避免加法溢出
int[][] dist = new int[n][n];
for (int[] row : dist) Arrays.fill(row, INF);
for (int i = 0; i < n; i++) dist[i][i] = 0;
for (int[] e : edges) dist[e[0]][e[1]] = Math.min(dist[e[0]][e[1]], e[2]);
for (int k = 0; k < n; k++) { // 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];
}
}
}
}
return dist;
}#include <vector>
#include <queue>
#include <climits>
using namespace std;
// Dijkstra 堆优化：单源最短路，要求边权非负
vector<long long> dijkstra(int n, vector<vector<int>>& edges, int src) {
vector<vector<pair<int,int>>> g(n);
for (auto& e : edges) g[e[0]].push_back({e[1], e[2]});
vector<long long> dist(n, LLONG_MAX);
dist[src] = 0;
// 最小堆：(距离, 节点)
priority_queue<pair<long long,int>,
vector<pair<long long,int>>,
greater<>> pq;
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue; // 懒删除
for (auto& [v, w] : g[u]) {
long long nd = d + w;
if (nd < dist[v]) {
dist[v] = nd;
pq.push({nd, v});
}
}
}
return dist;
}
// Bellman-Ford 带边数限制
vector<int> bellmanFordK(int n, vector<vector<int>>& edges, int src, int k) {
const int INF = INT_MAX;
vector<int> dist(n, INF);
dist[src] = 0;
for (int i = 0; i < k; i++) {
vector<int> prev = dist;
for (auto& e : edges) {
int u = e[0], v = e[1], w = e[2];
if (prev[u] != INF && prev[u] + w < dist[v]) {
dist[v] = prev[u] + w;
}
}
}
return dist;
}
// Floyd-Warshall：全源最短路，返回 n × n 距离矩阵
vector<vector<int>> floyd(int n, vector<vector<int>>& edges) {
const int INF = INT_MAX / 2; // 避免加法溢出
vector<vector<int>> dist(n, vector<int>(n, INF));
for (int i = 0; i < n; i++) dist[i][i] = 0;
for (auto& e : edges) dist[e[0]][e[1]] = min(dist[e[0]][e[1]], e[2]);
for (int k = 0; k < n; k++) { // 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];
}
}
}
}
return dist;
}模板里要注意四点：
- 懒删除不可省略：
if d > dist[u]: continue这一行决定了 Dijkstra 的复杂度。漏了算法结果仍正确（过期记录的松弛是无害的），但堆里会反复处理过期副本，复杂度退化。 INF的取值：Dijkstra 用Long.MAX_VALUE/LLONG_MAX没问题（不会加法溢出，因为有非负边权和nd < dist[v]短路）；Floyd 三层循环里dist[i][k] + dist[k][j]容易爆 int，建议用INT_MAX / 2或long long。- Bellman-Ford 拍照：带边数限制时必须用
prev = dist.clone()。否则同一轮内连续松弛会让一个节点"前进多步"，相当于一轮走了多条边，违反"k 轮 = 最多 k 条边"的语义。 - 节点编号：模板按 0..n-1 写。LeetCode 题目里若编号从 1 开始（如 LC 743），要么把数组开成
n + 1大、要么减一映射，别混用。
3. 母题精讲
LeetCode 743. 网络延迟时间
链接：LeetCode 743
题意：n 个网络节点，编号 1 到 n。给一组有向带权边 times[i] = [u, v, w]，表示信号从节点 u 传到 v 需要 w 单位时间。从源点 k 同时向所有可达节点广播信号，问全部节点收到信号需要多久。如果有节点收不到，返回 -1。
数据范围：
n：1 到 100times.length：1 到 60001 ≤ w ≤ 100
示例：
输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2
解释：从 2 到 1 是 1、到 3 是 1、再从 3 到 4 是 2。最远到 4，耗时 2。这件事换个说法是：从 k 出发，求到每个节点的最短路径长度，取最大值。如果某个节点不可达，答案是 -1。
暴力思路：把 BFS 当最短路用
上一章 DFS / BFS 与拓扑排序 里 BFS 按层扩张，"层数"就是到起点的距离。可是 BFS 里每条边的"距离"默认是 1——这道题的边带权 w，不是固定 1。如果硬把 BFS 套上去，能得到什么？
一种最直觉的修法：维护一个 dist[]，初始全是无穷大；从 k 出发跑 BFS，每次松弛 dist[v] = min(dist[v], dist[u] + w(u, v))。但这样的 BFS 不再"按层"——一个节点可能被多次入队、每次得到一个更短的距离。
from collections import defaultdict, deque
def bfs_relax(n, k, times):
g = defaultdict(list)
for u, v, w in times:
g[u].append((v, w))
dist = [float('inf')] * (n + 1)
dist[k] = 0
q = deque([k])
while q:
u = q.popleft()
for v, w in g[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w # 松弛成功
q.append(v) # 这里可能重复入队
return dist这本质是 Bellman-Ford / SPFA 的思路——每条边可能被反复松弛。在最坏情况（稠密图 + 边权差异大）下，一个节点可能入队 O(V) 次，每次又触发一轮邻居松弛，总复杂度 O(V × E)。n = 100, E = 6000 还过得去，但题目上界稍微一抬就崩——LC 787 类似问题里 V × E 是 10⁴ × 10⁵，直接超时。
更关键的浪费在于：这种 BFS 没有"全局最优"的保证。它只是反复松弛、直到不再变化为止。如果用对优先策略——每次拿"目前已知距离最小的未确定节点"扩展——就能保证它的最短距离已经确定了。这就是 Dijkstra。
关键观察：边权非负 ⇒ 第一次出堆即最短
Dijkstra 的核心是一句话：边权非负时，第一次从堆中弹出的距离值就是该节点的最短距离。
为什么？反证。假设节点 v 第一次出堆时 dist[v] = d，但真正最短距离是 d' < d。那 v 到 d' 的路径上必有一个中间节点 u，且 u 在 v 之前出堆（因为最短路径上 u 比 v 离源点更近，且边权非负意味着 dist[u] ≤ d' < d）。但 u 出堆时会松弛它的所有邻居——包括 v——所以 v 在堆里的距离至少会更新成 dist[u] + w(u, v) ≤ d'。这跟假设"v 出堆时距离是 d > d'"矛盾。
所以算法骨架：
- 维护
dist[]，初始全是无穷大，dist[k] = 0 - 用最小堆维护"待确认"的
(dist, node) - 每次从堆顶弹一个，如果是过期记录（
dist比当前dist[node]大）就跳过；否则它的dist[node]已经是最短的，松弛它的所有出边邻居入堆 - 重复直到堆空
每个节点最终被"确认"一次。每条边至多被松弛一次（出节点确认后）。堆操作 O(log V)。总复杂度 O((V + E) log V)。
下面用示例 times = [[2,1,1],[2,3,1],[3,4,1]], k = 2 走一遍。建邻接表：2 → 1 (w=1), 2 → 3 (w=1), 3 → 4 (w=1)。
Dijkstra 在 LC 743 上的执行
节点 1..4，源点 k=2。颜色：白=未访问，金=当前出堆并确认，蓝=已确认最短距离
最终答案 max(dist[1..n]) = 2。如果有节点的 dist 还是无穷大，说明不可达，返回 -1。
整个过程节点 1、2、3、4 各出堆一次，边 (2,1), (2,3), (3,4) 各松弛一次。总复杂度 O((V + E) log V)。
4. 例题（三道）
按"算法主线递进"排：标准 Dijkstra → 带边数限制的 Bellman-Ford → Dijkstra 包在动态图类里。每道带 follow-up 续到下一题。
4.1 LC 743 网络延迟时间
链接：LeetCode 743
回到本章开头那道题。建邻接表 + 跑一遍 Dijkstra + 取 dist[1..n] 的最大值。如果最大值是无穷大，说明有节点不可达，返回 -1。
import heapq
from collections import defaultdict
class Solution:
def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
g = defaultdict(list)
for u, v, w in times:
g[u].append((v, w))
INF = float('inf')
dist = [INF] * (n + 1)
dist[k] = 0
pq = [(0, k)] # (距离, 节点)
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]: # 过期记录跳过
continue
for v, w in g[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(pq, (nd, v))
ans = max(dist[1:]) # 节点编号从 1
return ans if ans < INF else -1class Solution {
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 INF = Integer.MAX_VALUE;
int[] dist = new int[n + 1];
Arrays.fill(dist, INF);
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[] nb : g[u]) {
int v = nb[0], w = nb[1];
if (d + w < dist[v]) {
dist[v] = d + w;
pq.offer(new int[]{d + w, v});
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (dist[i] == INF) return -1;
ans = Math.max(ans, dist[i]);
}
return ans;
}
}class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<vector<pair<int,int>>> g(n + 1);
for (auto& t : times) g[t[0]].push_back({t[1], t[2]});
const int INF = INT_MAX;
vector<int> dist(n + 1, INF);
dist[k] = 0;
// 小顶堆：(距离, 节点)
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
pq.push({0, k});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue; // 过期记录
for (auto& [v, w] : g[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
pq.push({d + w, v});
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (dist[i] == INF) return -1;
ans = max(ans, dist[i]);
}
return ans;
}
};复杂度：时间 O((V + E) log V)、空间 O(V + E)。V = n + 1、E = times.length。堆最坏装 O(E) 条记录（每次松弛成功就 push 一次），每次 log E ≈ log V（因为 E ≤ V²）。
几个细节：
- 节点编号从 1。
dist数组开n + 1大小、答案对dist[1:]取 max。开n长度会漏掉节点n本身。 - 不可达判定。最后一行检查
max(dist[1:])是不是INF，是的话说明有节点没被弹出过——返回-1。Java 写法是在循环里随时检查。 - 懒删除而不是真删除。Python
heapq没有 "decrease key" 操作，所以同一个节点可能被 push 多次（每次松弛成功就 push）。出堆时如果d > dist[u]，这就是过期记录，跳过。这是 Python / Java / Go 里 Dijkstra 的标准写法。
Follow-up：LC 743 边权非负，Dijkstra 直接套。如果题目改成"最多经过 k 条边"——比如限制只能转 1 次机——Dijkstra 还能直接用吗？
4.2 LC 787 K 站中转内最便宜的航班
链接：LeetCode 787
题意：n 个城市，编号 0 到 n − 1。给一组有向航班 flights[i] = [from, to, price]。求从 src 出发到 dst 的最便宜价格，但中转站数不能超过 k——也就是说从 src 出发最多经过 k + 1 条边到达 dst。如果不可能，返回 -1。
数据范围：
n：1 到 100flights.length：0 到n × (n − 1) / 20 ≤ src, dst, k < n，src ≠ dst1 ≤ price ≤ 10⁴
示例：
输入：n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]],
src = 0, dst = 3, k = 1
输出：700
解释：0 → 1 → 3 经过 1 次中转、总价 700。
0 → 1 → 2 → 3 总价 400 但中转 2 次，超出 k=1 不允许。这道题加了"边数 ≤ k + 1"的硬约束，Dijkstra 直接套会出错——Dijkstra 的"第一次出堆即最短"基于"距离单调递增"，但这道题的"最短"被边数限制截断了。
正确做法是 Bellman-Ford 跑 k + 1 轮。第 i 轮的 dist[v] 含义是"最多经过 i 条边时从 src 到 v 的最便宜价格"。每轮要用上一轮的 dist 副本松弛——否则同一轮内可能链式松弛多步、变相多走几条边。
class Solution:
def findCheapestPrice(self, n: int, flights: list[list[int]],
src: int, dst: int, k: int) -> int:
INF = float('inf')
dist = [INF] * n
dist[src] = 0
for _ in range(k + 1): # 最多 k+1 条边
prev = dist[:] # 拍照上一轮
for u, v, w in flights:
if prev[u] + w < dist[v]:
dist[v] = prev[u] + w
return dist[dst] if dist[dst] < INF else -1class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
int INF = Integer.MAX_VALUE;
int[] dist = new int[n];
Arrays.fill(dist, INF);
dist[src] = 0;
for (int i = 0; i <= k; i++) {
int[] prev = dist.clone();
for (int[] e : flights) {
int u = e[0], v = e[1], w = e[2];
if (prev[u] != INF && prev[u] + w < dist[v]) {
dist[v] = prev[u] + w;
}
}
}
return dist[dst] == INF ? -1 : dist[dst];
}
}class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
const int INF = INT_MAX;
vector<int> dist(n, INF);
dist[src] = 0;
for (int i = 0; i <= k; i++) { // 最多 k+1 条边
vector<int> prev = dist; // 拍照上一轮
for (auto& e : flights) {
int u = e[0], v = e[1], w = e[2];
if (prev[u] != INF && prev[u] + w < dist[v]) {
dist[v] = prev[u] + w;
}
}
}
return dist[dst] == INF ? -1 : dist[dst];
}
};复杂度：时间 O(k × E)、空间 O(n)。本题 k ≤ n − 1 = 99、E ≤ n × (n − 1) / 2 ≈ 5000，总操作量 5 × 10⁵ 级别。
为什么必须用 prev = dist[:] 拍照？看反例：本轮中如果先松弛了边 (src, a) 让 dist[a] 变小，再松弛 (a, b) 又用了本轮刚更新的 dist[a]——这样 b 实际是经过两条边到达的，但算法以为只用了一条。prev 拍照保证一轮内每个节点只"前进一步"。
另一种解法是带"剩余步数"的 Dijkstra：状态扩展成 (cost, node, edges_used)，剩余可走边数 < 0 时不继续。但用堆排序意义不大（剩余步数和 cost 的优先级冲突），常退化成 BFS。Bellman-Ford 在这道题里更自然。
Follow-up：上面两题都把"建图 + 跑算法"一次性写完。如果题目让你做一个图类——支持加边、查最短路这两个操作循环调用呢？
4.3 LC 2642 设计可以求最短路径的图类
题意：实现一个 Graph 类，支持：
Graph(int n, int[][] edges)：初始化n个节点的有向带权图，初始边为edges[i] = [from, to, weight]。addEdge(int[] edge)：添加一条有向边edge = [from, to, weight]。shortestPath(int node1, int node2)：返回从node1到node2的最短路径长度。如果不可达，返回-1。
数据范围：
n：1 到 100- 初始边数 + addEdge 调用次数：1 到
100 - shortestPath 调用次数：1 到
100 1 ≤ weight ≤ 10⁶
示例：
g = Graph(4, [[0,2,5],[0,1,2],[1,2,1],[3,0,3]])
g.shortestPath(3, 2) // 返回 6：3 → 0 → 1 → 2，3+2+1=6
g.shortestPath(0, 3) // 返回 -1：从 0 无法到 3
g.addEdge([1, 3, 4])
g.shortestPath(0, 3) // 返回 6：0 → 1 → 3，2+4=6关键决策：是预处理 Floyd O(V³) 一次性算好全源最短路，还是每次查询跑一次 Dijkstra？
- Floyd 预处理
O(V³)，每次shortestPath是O(1)，但addEdge之后要重跑——addEdge调用 100 次就是100 × V³ = 100 × 10⁶，刚好能过但常数大。 - Dijkstra：
addEdge是O(1)（只 push 到邻接表），shortestPath是O((V + E) log V) ≈ 100 × 8 = 800。总查询代价100 × 800 = 8 × 10⁴。
Dijkstra 显然更优：addEdge 远比 shortestPath 廉价，而题目允许两类调用各 100 次。下面给 Dijkstra 版本。
import heapq
class Graph:
def __init__(self, n: int, edges: list[list[int]]):
self.n = n
self.g = [[] for _ in range(n)]
for u, v, w in edges:
self.g[u].append((v, w))
def addEdge(self, edge: list[int]) -> None:
u, v, w = edge
self.g[u].append((v, w))
def shortestPath(self, node1: int, node2: int) -> int:
INF = float('inf')
dist = [INF] * self.n
dist[node1] = 0
pq = [(0, node1)]
while pq:
d, u = heapq.heappop(pq)
if u == node2: # 提前返回：目标节点出堆
return d
if d > dist[u]:
continue
for v, w in self.g[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(pq, (nd, v))
return -1 # 目标从未出堆 = 不可达class Graph {
private int n;
private List<int[]>[] g;
public Graph(int n, int[][] edges) {
this.n = n;
g = new List[n];
for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
for (int[] e : edges) g[e[0]].add(new int[]{e[1], e[2]});
}
public void addEdge(int[] edge) {
g[edge[0]].add(new int[]{edge[1], edge[2]});
}
public int shortestPath(int node1, int node2) {
long INF = Long.MAX_VALUE;
long[] dist = new long[n];
Arrays.fill(dist, INF);
dist[node1] = 0;
PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
pq.offer(new long[]{0, node1});
while (!pq.isEmpty()) {
long[] cur = pq.poll();
long d = cur[0];
int u = (int) cur[1];
if (u == node2) return (int) d; // 目标出堆即返回
if (d > dist[u]) continue;
for (int[] nb : g[u]) {
int v = nb[0], w = nb[1];
if (d + w < dist[v]) {
dist[v] = d + w;
pq.offer(new long[]{d + w, v});
}
}
}
return -1;
}
}class Graph {
int n;
vector<vector<pair<int,int>>> g; // g[u] = {(v, w)}
public:
Graph(int n, vector<vector<int>>& edges) : n(n), g(n) {
for (auto& e : edges) g[e[0]].push_back({e[1], e[2]});
}
void addEdge(vector<int> edge) {
g[edge[0]].push_back({edge[1], edge[2]});
}
int shortestPath(int node1, int node2) {
const int INF = INT_MAX;
vector<int> dist(n, INF);
dist[node1] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
pq.push({0, node1});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (u == node2) return d; // 目标出堆即返回
if (d > dist[u]) continue;
for (auto& [v, w] : g[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
pq.push({d + w, v});
}
}
}
return -1; // 不可达
}
};复杂度：构造 O(E)、addEdge O(1)、单次 shortestPath O((V + E) log V)。
两个收尾优化：
- 目标出堆即返回。Dijkstra 一旦从堆里弹出
node2，d就是最短距离——不用跑完整个堆。这是 Dijkstra 在"查单点最短距离"场景的标准提前退出。 - 不可达返回 -1。整个堆跑空
node2还没出堆过，意味着图里没有路径，返回-1。注意不要把"dist[node2] == INF"作为最终判据——目标节点出堆前可能已被一条次优路径松弛过dist[node2]，但实际最短就是次优值（这里返回的d才对）。
如果题目把 addEdge 改成"修改边权"（包括减小），Dijkstra 就要从头跑——因为减小边权可能让旧的最短路过期。这道题只允许新增边（权值正），所以已有的 dist 不会失效，但每次查询仍然要重跑 Dijkstra，没法增量维护。
5. 边界、易错与复杂度
Dijkstra 的"过期记录"
Python heapq / Java PriorityQueue / Go container/heap 都不支持 "decrease key"，所以同一节点会被 push 多次。出堆时必须检查 if d > dist[u]: continue——这是 Dijkstra 写错最常见的地方之一。漏了这一行算法结果仍然对（过期记录的松弛是无害的），但复杂度从 O((V + E) log V) 退化到 O(E log E) 乘以堆里的过期副本数，最坏 O(E² log E) 直接 TLE。
Bellman-Ford 一轮内的串味
带边数限制的 Bellman-Ford 必须用 prev = dist[:] 拍照。LC 787 反例：
flights = [[0,1,1],[1,2,1]], src=0, dst=2, k=0k = 0 意味着只能直飞、不能中转。直观答案是 -1（没有 0 → 2 的直飞）。
不拍照的版本：第 1 轮里先松弛 (0,1) 让 dist[1] = 1；接着同一轮松弛 (1,2) 用了本轮刚算好的 dist[1]，得到 dist[2] = 2。算法以为 0 到 2 经过 1 条边就能到，错。
拍照版本：第 1 轮 prev[1] = INF，松弛 (1,2) 时 prev[1] + w = INF，dist[2] 不更新，正确返回 -1。
Floyd 的整数溢出
Floyd 三层循环里 dist[i][k] + dist[k][j] 容易溢出 int 上限。两种解决：
- 用
long存（Java / Go） INF设小一点，比如Integer.MAX_VALUE / 2，让 "INF + INF" 不溢出
第二种更简洁，多数题里 V³ × max_weight ≪ 10⁹ 完全够。
Dijkstra vs Bellman-Ford 的选择
- 边权全正 → Dijkstra（
O((V + E) log V)） - 边权可能为负 → Bellman-Ford / SPFA（
O(V × E)） - 要检测负环 → 必须 Bellman-Ford
- 有"边数 ≤ k"约束 → 必须 Bellman-Ford 跑 k 轮（Dijkstra 不行）
- 全源最短路 + V 小 → Floyd（
O(V³)），写起来比 V 遍 Dijkstra 简单
Dijkstra 的"提前返回"
只需要单点最短距离时，目标节点出堆瞬间就能返回。但有些场景不能提前返回：
- 同时要所有节点的距离（如 LC 743）
- 要数最短路径条数（要等所有等长路径都松弛完，如 LC 1976）
写代码前先想清楚是查单点还是查全表，免得提前 return 漏算其他节点。
复杂度速查
| 题 | 算法 | 时间 | 空间 |
|---|---|---|---|
| LC 743 网络延迟 | Dijkstra 堆 | O((V + E) log V) | O(V + E) |
| LC 787 K 中转 | Bellman-Ford 跑 k+1 轮 | O(k × E) | O(V) |
| LC 2642 图类 | Dijkstra 堆 / 查询 | 单次 O((V + E) log V) | O(V + E) |
7. 按边权特征选算法 + 与其他图算法的关系
按边权特征选算法
最短路算法选型其实就看边权长什么样：
| 边权类型 | 选哪个 | 复杂度 |
|---|---|---|
| 全 1（无权图） | 普通 BFS | O(V + E) |
| ∈ 1 | 0-1 BFS（双端队列，0 边推前、1 边推后） | O(V + E) |
| 非负实数 | Dijkstra + 堆 | O((V+E) log V) |
| 含负权（无负环） | Bellman-Ford / SPFA | O(VE) |
| 全源 + V 小 | Floyd-Warshall | O(V³) |
| 网格 + 启发式估价 | A* = Dijkstra + h(n) | 视 heuristic 而定 |
0-1 BFS 是个常被忽略的好工具——LC 2290 / LC 1368 都是它的典型场景，比上 Dijkstra 常数小一个数量级。
与最小生成树、网络流、A* 的关系
最短路、MST、网络流是同一族"图上贪心 / 松弛"问题的三个不同切面，可以放在一张表对比：
| 算法族 | 优化目标 | 贪心选择 | 代表算法 |
|---|---|---|---|
| 最短路 | Σ w 路径最小 | 选 dist[v] 最小的未确认节点 | Dijkstra |
| 最小生成树 | Σ w 树最小 | 选权重最小的未连接边 | Prim / Kruskal |
| 最大流 | Σ flow 流最大 | 选含可行增广路 | Ford-Fulkerson / Dinic |
| A* 启发式 | Σ w + h 最小 | 选 dist + h 最小（h 是估价） | A* |
Prim 算法的实现骨架几乎和 Dijkstra 一模一样——把 priority = dist[v] 改成 priority = edge_weight、把 relax(u, v, w) 改成 update(v, w) 就行。A* 进一步把 Dijkstra 的 priority 改成 dist + h(v)，在网格寻路（LC 1091 / 1631）里能大幅剪枝。
8. 小结
最短路三件套对应三种场景：
- Dijkstra（堆优化
O((V + E) log V)）：非负权、单源——LC 最短路题里最常考的一类。"过期记录跳过 + 入堆即松弛"是模板。 - Bellman-Ford / SPFA（
O(V × E)）：允许负权、能检测负环、能限制"边数 ≤ k"。LC 787 是边数限制的代表题。 - Floyd-Warshall（
O(V³)）：全源最短路、V小时（通常≤ 400）首选。三层循环写起来不容易出错。
跳出最短路这个具体问题，更通用的两条思路：
- 状态扩展：当原始图的最短路不够用时（比如带
k步限制），把状态从(节点)升到(节点, 剩余步数)或(节点, 边数 mod 2)。LC 787 / LC 864（钥匙状态）都是这套。 - 最短路 + DP：Dijkstra 算完距离后按
dist升序做 DP。LC 1786 / LC 1976 都用到。本质是利用"dist的 DAG 偏序"。
下一节会讲 最小生成树 与并查集——Kruskal / Prim 都和 Dijkstra 共享"堆 + 邻接表"的骨架，跳过来很顺手。
对应灵神题单：图论 · 最短路 / Dijkstra / Bellman-Ford / Floyd
进一步阅读：灵茶山艾府《图论题单》；LeetCode 最短路标签 高频题