题目描述
思路解析动画文字版
普通 Dijkstra 只看价格，可能超过中转次数。
做 K+1 轮松弛，每轮只基于上一轮价格，保证最多使用指定条数的边。
1. 航班图 + Bellman-Ford：求 0→2、最多中转 K=1 站的最便宜票价。航班：0→1(100)、1→2(100)、0→2(500)。Bellman-Ford：做 K+1=2 轮松弛，第 r 轮只允许「最多 r 段航班」的路线 → 天然限制中转次数。初始 dist=[0, ∞, ∞]。
2. 第 1 轮 · 最多 1 段航班：第 1 轮(最多飞 1 段)：松弛所有边。0→1 → dist[1]=100；0→2 → dist[2]=500。dist=[0, 100, 500]。
3. 第 2 轮 · 最多 2 段=1 次中转：第 2 轮(最多飞 2 段=1 次中转)：基于上一轮的 dist 快照再松弛。0→1→2 = 100+100 = 200 ＜ 500 → dist[2] 更新为 200。dist=[0, 100, 200]。
4. 关键帧 · 快照限制段数：关键帧：每轮只基于「上一轮的快照 nxt」松弛，保证第 r 轮的结果最多用 r 段航班，从而把中转次数卡在 K 以内。答案 dist[2]=200(0→1→2，恰 1 次中转，比直飞 500 便宜)。
一句话记住：做 K+1 轮松弛，每轮只基于上一轮价格，保证最多使用指定条数的边。
边界三连：三种边界先想清楚。
面试追问 1：核心思路。
面试追问 2：复杂度分析。
面试追问 3：Dijkstra 要带 stops 状态。
这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=graph 连刷同类题；卡住时用 AI 答疑问“我的状态定义哪里不稳”。
参考代码
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]复杂度
- 时间复杂度：O(K·E)，K+1 轮，每轮遍历所有 E 条边
- 空间复杂度：O(n)，dist / nxt 数组，各 n 个
可套用的代码模板
骨架：K+1 轮松弛，每轮用上一轮快照，限制最多飞 K+1 段。
Python
# K 站中转骨架 · Bellman-Forddist = [INF]*n; dist[src] = 0for _ 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 = nxtreturn -1 if dist[dst]==INF else dist[dst]易错点
面试追问把动画讲成自己的话
追问核心思路是什么？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题