LeetCode 787中等高级图
K 站中转内最便宜的航班 图解题解
这道题到底在问什么
在最多 K 次中转内，从 src 到 dst 的最低价格。
- 示例
- n=3, flights=[[0,1,100],[1,2,100],[0,2,500]], K=1 → 200
最优解：一步一步想明白
- 3普通 Dijkstra 只看价格，可能超过中转次数。
- 4做 K+1 轮松弛，每轮只基于上一轮价格，保证最多使用指定条数的边。
- 5求 0→2、最多中转 K=1 站的最便宜票价。航班：0→1(100)、1→2(100)、0→2(500)。Bellman-Ford：做 K+1=2 轮松弛，第 r 轮只允许「最多 r 段航班」的路线 → 天然限制中转次数。初始 dist=[0, ∞, ∞]。
- 6第 1 轮(最多飞 1 段)：松弛所有边。0→1 → dist[1]=100；0→2 → dist[2]=500。dist=[0, 100, 500]。
- 7第 2 轮(最多飞 2 段=1 次中转)：基于上一轮的 dist 快照再松弛。0→1→2 = 100+100 = 200 ＜ 500 → dist[2] 更新为 200。dist=[0, 100, 200]。
- 8关键帧：每轮只基于「上一轮的快照 nxt」松弛，保证第 r 轮的结果最多用 r 段航班，从而把中转次数卡在 K 以内。答案 dist[2]=200(0→1→2，恰 1 次中转，比直飞 500 便宜)。
- 11一句话记住：做 K+1 轮松弛，每轮只基于上一轮价格，保证最多使用指定条数的边。
- 20这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=graph 连刷同类题；卡住时用 AI 答疑问“我的状态定义哪里不稳”。
⚠️ 容易写错的地方
✗ 错：用普通 Dijkstra 不限中转
✓ 对：Bellman-Ford 按轮数限制段数
普通 Dijkstra 求无约束最短路，可能用超过 K 次中转，不满足题意。
✗ 错：同一轮内用刚更新的 dist
✓ 对：用上一轮快照 nxt 松弛
就地更新会让一轮内连用多条边，等于放开了中转限制。
✗ 错：轮数算错
✓ 对：做 K+1 轮(K 次中转 = K+1 段航班)
K 站中转对应最多 K+1 段飞行，每轮加一段，所以 K+1 轮。
完整代码（Python / C++ / Java）
Python
class Solution:
def findCheapestPrice(self, n, flights, src, dst, k):
INF = 10**15
dist = [INF] * n
dist[src] = 0
for _ in range(k + 1):
nxt = dist[:]
for a, b, price in flights:
if dist[a] != INF and dist[a] + price < nxt[b]:
nxt[b] = dist[a] + price
dist = nxt
return -1 if dist[dst] == INF else dist[dst]C++
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
const int INF = 1e9;
vector<int> dist(n, INF);
dist[src] = 0;
for (int step=0; step<=k; step++) {
vector<int> nxt = dist;
for (auto& f : flights) {
if (dist[f[0]] != INF) nxt[f[1]] = min(nxt[f[1]], dist[f[0]] + f[2]);
}
dist.swap(nxt);
}
return dist[dst] == INF ? -1 : dist[dst];
}
};Java
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
int INF = 1_000_000_000;
int[] dist = new int[n];
Arrays.fill(dist, INF);
dist[src] = 0;
for (int step=0; step<=k; step++) {
int[] next = dist.clone();
for (int[] f: flights) if (dist[f[0]] != INF) next[f[1]] = Math.min(next[f[1]], dist[f[0]] + f[2]);
dist = next;
}
return dist[dst] == INF ? -1 : dist[dst];
}
}套路模板 · Bellman-Ford 限轮数
# K 站中转骨架 · Bellman-Ford
dist = [INF]*n; dist[src] = 0
for _ in range(k + 1): # K+1 轮 = 最多 K+1 段航班
nxt = dist[:] # 关键: 用上一轮快照
for a, b, price in flights:
if dist[a] != INF and dist[a] + price < nxt[b]: # 防 INF 溢出
nxt[b] = dist[a] + price
dist = nxt
return -1 if dist[dst]==INF else dist[dst]复杂度
时间复杂度
O(K·E)
K+1 轮，每轮遍历所有 E 条边
空间复杂度
O(n)
dist / nxt 数组，各 n 个
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 K 站中转内最便宜的航班 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
核心思路是什么？+
Bellman-Ford 做 K+1 轮松弛，每轮基于上一轮 dist 快照(nxt)更新；第 r 轮的结果最多用 r 段航班，从而把中转次数限制在 K 以内。
这道题为什么用「高级图」，换最直接的暴力解会差在哪？+
高级图抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。