逐层扩展为什么能找到最短路径

展示一张小网格地图，起点在左上、终点在右下，用动画示意从起点"一圈一圈"向外扩散的波前。提出驱动问题：第一次到达终点时，所走的路为什么一定是最短？

• 起点同时向四个方向扩展
• 波前像水面涟漪一样扩散
• 第一次碰到终点就停下——为什么这就是最短？

在学习任何解释之前，先让学习者选一个最符合直觉的猜测。

• 选择一个最接近直觉的解释
• 解释会在后续场景中揭晓

提供一个可交互的网格模拟器：起点和终点可拖动，可放置/擦除障碍。点击"开始"后逐层显示从起点出发的波前（每层用不同颜色），并记录"当前波前距离"。学习者可在多个布局上观察：终点被首次点亮时，路径长度是否等于最短距离。

• 拖动起点、终点、障碍
• 逐层推进可视化波前
• 观察终点首次点亮时的距离

用一张静态图清晰展示：从起点出发，长度为 1 的路径有 4 条、长度为 2 的路径有 12 条……逐层波前恰好就是按路径长度 k 把所有长度为 k 的路径一次性铺开。

• 第 k 层 = 所有长度为 k 的路径
• 波前层数 = 当前已知的最短路径长度
• 终点首次被覆盖 = 找到最短路径

用两步论证：(1) 任何长度为 k 的路径必然经过某一长度为 k−1 的中间节点，因此它最晚在第 k 层波前被点亮；(2) 反过来，第 k 层点亮的节点一定存在一条长度为 k 的路径。所以波前按层数严格等价于按路径长度。

• 长度 k 的路径 = 长度 k−1 的节点 + 一步
• 波前第 k 层 = 首次可达的长度 k 路径
• 终点首次进入第 k 层 ⇒ 不存在更短路径

把同样的"逐层扩展"思想搬到加权图上：每条边写有正权重。学习者可以拖动滑条改变波前推进规则（按边数 vs. 按权重累积），观察终点首次被点亮时是否仍是最短路径——为下一节埋下边界。

• 切换"按层数扩展"与"按权重扩展"
• 观察两种规则下终点首次点亮距离的差异
• 引出下一节的边界条件

明确逐层扩展保证最短路径的两个关键前提：(1) 所有"一步"的代价相同（如无权图、单位权网格）；(2) 不允许负权边。一旦代价不等或出现负权，单纯按层数扩展就不再等价于按长度扩展，需要换成 Dijkstra / Bellman-Ford。

• 前提 1：每步代价相同
• 前提 2：无负权边
• 超出前提时需要不同的算法

直接回答：逐层扩展按路径长度递增枚举所有从起点出发的路径，因此终点首次被波前覆盖时，所走路径长度就是全局最短。联系到 BFS 与 Dijkstra，指出"逐层"是把搜索顺序和路径长度对齐的关键技巧。

• 逐层扩展 = 按路径长度从小到大枚举
• 终点首次到达 ⇒ 路径最短
• BFS / Dijkstra 的本质都是这种对齐