知识点深化 · 图最短路径
图最短路径：地图导航背后的算法
地图导航、外卖派单、网络路由，都在问同一个问题：从 A 到 B 怎么走最短？这就是图最短路径。无权图用 BFS，非负权用 Dijkstra，有负权用 Bellman-Ford。这一页搞懂贪心、优先队列和松弛操作，你就能亲手推出一条最短路。
① 小白第一课怎么学（4 步走，约 55 分钟）
地图导航找最短路线，就是图最短路径问题：
1看直观（10 分钟）
读第②③部分：把 Dijkstra 想象成"从起点一圈圈往外扩，先确定最近的"。
2记算法（15 分钟）
背第④部分：BFS、Dijkstra、优先队列、负权 Bellman-Ford。
3走例题（15 分钟）
精读第⑤部分，手推一遍 Dijkstra。
4刷题纠错（15 分钟）
做第⑦⑩部分，错题回到第⑥部分。
本课小目标学完你要能：① 知道无权图用 BFS、非负权用 Dijkstra；② 说出 Dijkstra 每步在干嘛；③ 解释为什么有负权边不能用 Dijkstra。
② 一图看懂：最短路径算法怎么选
读法：边权都为 1 用 BFS；边权非负用 Dijkstra（贪心+优先队列+松弛）；有负权边用 Bellman-Ford。
③ 先认识它：Dijkstra 就是"从家一圈圈往外找最近"
想象从家（起点）出发找去公司的最短路：
· 先看离家最近的点，确认"到它的最短距离就是这么多"，以后不再改。
· 然后从这个点出发，更新它邻居的距离（发现更近的路就刷新）。
· 再从所有"还没确定"的点里挑距离最小的，确认它。
· 重复，直到所有点都被确认。这就是贪心：每次锁定最近的，不再回头。
用优先队列（最小堆）快速取出"当前距离最小的点"，就不用每次全表扫。
松弛 Relaxation核心一句话：dis[v] = min(dis[v], dis[u] + 边uv权)。发现"经过 u 到 v 更近"就更新 v 的距离。整个 Dijkstra 就是不断做松弛。
④ 完整体系与算法表
三种算法怎么选
| 算法 | 适用图 | 思想 | 复杂度 |
|---|
| BFS | 无权图（所有边权=1） | 层序扩展，第一次到就是最短 | O(V+E) |
| Dijkstra | 非负权图（边权≥0） | 贪心+优先队列+松弛 | O((V+E)logV) |
| Bellman-Ford | 可有负权边 | 对所有边松弛 V−1 轮 | O(VE) |
Dijkstra 步骤
标准流程
① dis[起点]=0，其余=∞ ② 从未确定点中取 dis 最小的 u
③ 标记 u 已确定 ④ 松弛 u 的所有邻居 v：dis[v]=min(dis[v],dis[u]+w(u,v)) ⑤ 重复②~④
为什么 Dijkstra 不能有负权边贪心假设"一旦确认某点距离就不会更短"。但负权边可能让之后绕一圈反而更近，这个假设就破了。有负权边要用 Bellman-Ford。
⑤ 应用场景与典型例题
例1（BFS）无权图，起点到终点隔两条边，最短路径长度是？
边数即距离。
BFS 一层层扩，第一次到达终点经过 2 条边，最短路=2。
例2（Dijkstra）起点 S 到 A=5，S 到 B=10，A 到终点=3，B 到终点=2，S 到终点最短路？
比较两条路。
· S→A→终点 = 5+3 = 8。
· S→B→终点 = 10+2 = 12。
最短是 8（走 A）。
例3（负权）一条边权是 −5，为什么 Dijkstra 会错？
负权让"已确认"的点可能被刷新。
Dijkstra 一旦确认某点距离就不再更新；但负权边可能让绕远路反而更近，导致已确认的值其实错了。这种情况要上 Bellman-Ford。
BFS 和 Dijkstra 关系BFS 其实是 Dijkstra 在"边权都=1"时的特例——按层扩展等价于按距离取最小。
⑥ 高频错误诊断（4 条）
错误 1：有权图乱用 BFSBFS 只在边权都相等（=1）时给最短路。边权不同必须用 Dijkstra。
错误 2：有负权边还用 Dijkstra负权会破坏贪心"确认即最优"的前提，结果是错的。
错误 3：忘记把起点初始化为 0、其余为 ∞初始化错了后面全错。dis[start]=0，其他先设无穷大。
错误 4：以为 Dijkstra 能处理负环负环（一圈总权为负）可以无限绕圈让距离变负，任何最短路算法都无解，Bellman-Ford 负责检测它。
⑦ 考点与真题演练（4 题）
考点分布
| 考法 | 出题形式 | 应对 |
|---|
| 算法选择 | 给图特征选算法 | 无权 BFS/非负 Dijkstra/负权 Bellman |
| Dijkstra 步骤 | 每步取哪个点 | 取未确定中距离最小 |
| 松弛 | 写更新式 | dis[v]=min(dis[v],dis[u]+w) |
真题1. 边权都为 1 的无权图求最短路，用什么？
真题2. Dijkstra 算法每步从"未确定点"中选哪个？
真题3. 图中存在负权边时，应选用？
真题4. 松弛操作的公式是？
⑧ 必背公式卡
无权图：BFS，第一次到即最短 O(V+E) 边权=1
非负权：Dijkstra O((V+E)logV) 贪心+优先队列
负权边：Bellman-Ford O(VE) 松弛 V−1 轮
松弛：dis[v]=min(dis[v],dis[u]+w) 发现更近就更新
Dijkstra 选点：取未确定中 dis 最小 贪心锁定
初始化：dis[start]=0，其余=∞ 别忘
负环：最短路不存在，Bellman-Ford 负责检测 绕圈无限小
⑨ 应用输出：用最短路径思维建模
建模场景：地图导航找最快路线
节点=路口，边=道路，边权=通行时间（非负）。
· 从家出发，用优先队列每次取出当前累计时间最短的路口。
· 到一个路口就松弛它能拐到的下一个路口。
· 第一次到达公司时，累计时间就是最短——这就是 Dijkstra。
· 若某条路是"下坡扣时间"（负权），就要换 Bellman-Ford。
口述训练说三句："无权用 BFS、非负权用 Dijkstra、负权用 Bellman-Ford；Dijkstra 每次取距离最小点并松弛邻居；松弛就是发现更近就更新。"
⑩ 分层练习 18 题（基础 6 + 中档 6 + 拔高 6）
▍基础 6 题
基础2非负权图最短路用什么？
Dijkstra。
基础3松弛操作是？
dis[v]=min(dis[v],dis[u]+w(u,v))。
基础4起点距离初始化为多少？
0，其余点为 ∞。
基础5Dijkstra 用什么数据结构快速取最小？
优先队列（最小堆）。
基础6有负权边用什么？
Bellman-Ford。
▍中档 6 题
中档7为什么 Dijkstra 用贪心是对的？
边权非负，一旦取到当前最小距离点，不可能再有更短路径到达它。
中档8S→A=4，A→T=2，S→T=10，S 到 T 最短路？
S→A→T=4+2=6 < 10，最短路 6。
中档9Dijkstra 复杂度（堆优化）？
O((V+E)logV)。
中档10BFS 为什么能求无权最短路？
按距离层序扩展，第一次到达某点经过边数最少。
中档11Bellman-Ford 为什么松弛 V−1 轮？
最短路最多含 V−1 条边，V−1 轮保证所有可能都被松弛。
中档12负环是什么？
一圈边权和为负的环，绕圈可无限减小距离，最短路无意义。
▍拔高 6 题
拔高13Dijkstra 为什么不能处理负权边？
贪心一旦确认点就不再更新，但负权边可能让绕远路更近，破坏"确认即最优"。
拔高14所有点对最短路用什么？
Floyd-Warshall O(V³)，动态规划三重循环。
拔高15Dijkstra 和 Prim（最小生成树）区别？
都贪心取最近点；Dijkstra 更新"到起点距离"，Prim 更新"到树的距离"。
拔高16为什么优先队列要存 (距离, 点)？
堆按距离排序，每次 O(logV) 取出当前最小距离的点。
拔高170-1 加权图（边权 0 或 1）最快算法？
0-1 BFS（双端队列），O(V+E)，比 Dijkstra 快。
拔高18拓扑排序能求 DAG 最短路吗？
能，按拓扑序松弛每条边，O(V+E)，且可处理负权边。
⑪ 记忆口诀 + 7 天复习计划
三句口诀
① 无权 BFS、非负 Dijkstra、负权 Bellman-Ford。
② Dijkstra：取最小距离点，松弛它的邻居。
③ 松弛就是 dis[v]=min(dis[v], dis[u]+w)。
| 天 | 任务 | 自检 |
|---|
| 第 1 天 | 读②③④，画 Dijkstra 流程 | 说清选点规则 |
| 第 2 天 | 背算法表 + 基础 1-6 | 三算法选对 |
| 第 3 天 | 做中档 7-12 | 手推一条最短路 |
| 第 4 天 | 做拔高 13-18 | 解释负权为什么不行 |
| 第 5 天 | 做⑦真题 4 题 | 限时每题 2 分钟 |
| 第 6-7 天 | 合上书口述三句口诀 | 不看资料全说对 |
← 返回算法与AI总览