13.2　无权最短路：BFS 的正确用法

学习目标：学完本节，你能

• 说清"最短路径"到底在最短什么，以及 BFS 保证的是哪一种；
• 用多源 BFS 一次求出"到最近源点"的距离，并说明它为什么成立；
• 说清双向 BFS 在什么图上快、在什么图上不快，而不是背一个倍率；
• 识别 BFS 失效的信号，并用 0-1 BFS 处理"边权只有 0 和 1"的中间情况。

先修：12.3（BFS 求最短路、双向 BFS 的理论推导）、13.1（拓扑排序）。 固定术语：最短路径（Shortest Path）、广度优先搜索、层、前驱数组。 环境与版本：.NET 8 / C# 12。 预计阅读：30 分钟。

一、直觉：BFS 已经会了，这一节讲什么？

12.3 节已经把 BFS 求最短路讲完了 —— 队列、dist、prev、为什么第一次到达就是最短、240 组暴力验证。

那这一节讲什么？ 讲三个"接下来"的问题 —— 它们是"会用 BFS"和"能在工程里用对 BFS"之间的差距：

小陈这次的活是外卖配送系统的"最近配送站" —— 用户下单后，系统要立刻回答"哪个站点离他最近、大概几站路"。

这个需求看起来就是 BFS —— 但坑在后面。

二、形式化：三种"最短"，别混为一谈

最短路径（Shortest Path）：在图中，从起点 $s$ 到终点 $t$ 的所有路径里，按某个度量衡最划算的那一条。

关键词是"按某个度量衡" —— 因为"最短"有不止一种定义：

这三行是整章的地图。 本节全部内容都在第一行里 —— 但会沿着第三列一路"差点越界"，为后两行做铺垫。

BFS 保证的是"边数最少"，仅此而已。

它没有"代价"这个概念 —— 每条边在它眼里都一样长。

为什么这个区别是致命的？ 下一小节最后会实测一个具体反例。

三、多源 BFS：一次遍历，所有起点

先说清楚问题：一个城市里有 $k$ 个配送站，要算出每个小区到"最近的"配送站有多少站路。

最直觉的做法是：对每个配送站各跑一次 BFS，得到 $k$ 个距离数组，再逐点取最小值。$k$ 个起点就 $k$ 倍代价。

但有个更省的做法 —— 多源 BFS：

static (int[] dist, long visited) MultiSourceBfs(Graph g, int[] sources)
{
    var dist = new int[g.VertexCount];
    Array.Fill(dist, -1);
    var queue = new Queue<int>();

    foreach (int s in sources)          // ★ 多源的关键：所有源点一起入队，距离都是 0
    {
        dist[s] = 0;
        queue.Enqueue(s);
    }

    while (queue.Count > 0)
    {
        int v = queue.Dequeue();
        foreach (int next in g.Neighbors(v))
        {
            if (dist[next] != -1) continue;
            dist[next] = dist[v] + 1;
            queue.Enqueue(next);
        }
    }
    return (dist, visited);
}

和单源 BFS 的差别只有一处：初始化时把所有源点一起入队，而不是只放一个。

为什么这样是对的？

想象所有配送站同时开始"向外扩散" —— 每个小区被第一个波前碰到时，那个波前来自的就是离它最近的那个站。

等价的说法：在原图上加一个虚拟源点 $S^*$，让它到每个真实源点都连一条边。 对这个加了虚拟点的图跑单源 BFS，$S^*$ 到 $v$ 的距离恰好是"$v$ 到最近源点的距离 + 1"。 而把所有源点直接入队，就是省掉了那个虚拟点。

实测（300×300 的网格城市，共 90,000 个小区，10 个配送站）：

  多源 BFS（所有配送站一起入队，只跑 1 次）：
    访问顶点数 = 90,000

  对照：10 个配送站各跑一次单源 BFS，再逐点取最小：
    访问顶点数 = 900,000（10 × 90,000）

  两种做法算出的距离数组完全一致：True
  访问顶点数之比：10.0 倍

注意这里的度量是"访问顶点数"，不是毫秒 —— 它与机器无关，你在任何电脑上跑都是这两个数（1.2 节、1.3 节的同一条原则）。

10.0 倍正好等于站点数，这不是巧合：单源 BFS 必须跑完整个连通分量才知道谁更近，而多源 BFS 跑一遍就够了。

什么时候该用多源 BFS？ 只要问题是"到最近的一堆东西"，它就是标准解法：

四、反预期实测：双向 BFS 那个"400 万倍"

12.3 节练习 12.3.5 推导过双向 BFS 的威力：单向要扩展 $b^d$ 个顶点，双向只要 $2b^{d/2}$ —— 对 $b=200$、$d=6$ 算出来是 400 万倍。

我当时把这个数字写进了正文，但心里没底 —— 因为它假设的是"每个顶点都有 $b$ 个孩子"，也就是一棵理想的多叉树。

真实的图不长那样。 于是我把双向 BFS 实现出来，在两种形状的图上各测一遍。

先看实现

static (int distance, long visited) BiBfs(Graph g, int start, int goal)
{
    var distF = new int[g.VertexCount];      // 从起点出发的距离
    var distB = new int[g.VertexCount];      // 从终点出发的距离
    Array.Fill(distF, -1);
    Array.Fill(distB, -1);
    distF[start] = 0; qF.Enqueue(start);
    distB[goal]  = 0; qB.Enqueue(goal);

    while (qF.Count > 0 && qB.Count > 0)
    {
        if (levelF + levelB >= best) break;  // 再扩展也不可能更短了

        if (levelF <= levelB) { Expand(qF, distF, distB); levelF++; }   // ★ 扩展层数少的一边
        else                  { Expand(qB, distB, distF); levelB++; }
    }
}

两个关键点（12.3 节提过，这里是代码落地）：

1. 每次扩展"已扩展层数较少"的那一边 —— 不能"两边各扩展一半"，因为两边的层不一定对齐。
2. Expand 里必须先取 queue.Count —— 那才是"扩展一层"（12.3 节的 levelSize 技巧，这里同样必需）。
3. 碰面的判定：某个顶点在 distF 和 distB 里都 != -1，则 distF[v] + distB[v] 是一条完整路径的长度。

再看实测

  ---------- 图 A：二维网格（500×500）----------
    起点 125250 → 终点 125450，真实距离 200
      单向 BFS：访问     81,003 个顶点
      双向 BFS：访问     37,801 个顶点
      提升 2.14 倍
      两者算出的距离一致：True

  ---------- 图 B：完全 3 叉树（深度 12）----------
    顶点数 797,161（每个非叶节点有 3 个孩子）
    起点 = 根 0 → 终点 = 最后一层的第一个叶子 265720，真实距离 12
      单向 BFS：访问    797,161 个顶点
      双向 BFS：访问      1,146 个顶点
      提升 695.6 倍
      两者算出的距离一致：True

同一个算法，两种图上差了 325 倍。

这是本节最重要的发现，也是 12.3 节那个"400 万倍"的真相：

双向 BFS 的指数级优势，只在"图像树一样向下指数分支"时才成立。

为什么网格图上只有 2 倍？ 因为网格里每一层是"一圈"，不是"一批"：

  单向：半径 200 的菱形，面积 ≈ 4 × (200²/2) = 80,000
  双向：两个半径 100 的小菱形，面积 ≈ 2 × 4 × (100²/2) = 40,000
  比值 ≈ 2

每一层的顶点数随 $d$ 线性增长，所以总面积是 $d^2$。 双向把 $d$ 砍成 $d/2$，面积只剩 1/4 —— 但要算两遍，所以最终只省一半。

而树上每一层的顶点数随 $d$ 指数增长，面积由最外层主导 —— 把深度砍半，节点数就直接开了平方根。

所以"双向 BFS 快 400 万倍"这句话，缺了一个前提：图必须是高分支、树状的（社交网络、魔方状态图、拼图状态图都属于这一类）。

在地图、网格这类"二维铺开"的图上，双向 BFS 就是快 2 倍左右 —— 有用，但远不是数量级的碾压。

这也解释了为什么地图导航的主力不是双向 BFS，而是 A*（用启发式把搜索导向目标方向）—— 方向比"两头搜"更值钱。

五、BFS 什么时候失效？

(A) 带权图：BFS 给出"步数最少、代价最大"的路径

看一个 5 个顶点的小图（括号里是边的代价）：

  S --100-- A --100-- T              2 步，总代价 200
  S ---1--- B ---1--- C ---1--- T    3 步，总代价 3

实测：

      BFS 给出的路径：S -> A -> T，2 步
        这条路的实际代价：200

      暴力枚举所有路径后的真正最优：S -> B -> C -> T，总代价 3

BFS 没有算错 —— 它如实回答了"哪条路边数最少"，2 步确实是最少的。

错的是把"边数最少"当成了"代价最小"。

这就是从"无权图"跨到"带权图"时发生的事：度量衡变了，算法的正确性就不再成立。

工程里的信号很明确：只要边上带了距离、耗时、费用、权重，BFS 立刻出局。

(B) 中间地带：边权只有 0 和 1

在跳到 Dijkstra 之前，先看一个很常见的中间情况 —— 边权只有两种取值：0 和 1。

例子：换乘网络里，"同站台换乘"代价 0，"坐一站"代价 1。或者游戏里"走平地"代价 1、"传送门"代价 0。

普通 BFS 处理不了（它认为所有边都是 1），但只需要把队列换成双端队列：

foreach (var (to, w) in adj[v])
{
    if (dist[v] + w >= dist[to]) continue;
    dist[to] = dist[v] + w;

    if (w == 0) deque.AddFirst(to);   // ★ 代价 0：插队首 —— 它不增加代价，应该【立刻】处理
    else        deque.AddLast(to);    // ★ 代价 1：插队尾 —— 和普通 BFS 一样排队
}

为什么这样是对的？ 因为代价只有两种：

队列里最多只会同时存在"代价 $d$"和"代价 $d+1$"两种顶点 —— 代价 0 的边插到队首，保证它在同一层内被优先处理完；代价 1 的边插到队尾，正好落到下一层。

双端队列刚好能表达"两个优先级"。

实测（20 张随机的 0/1 权图，每张与暴力枚举逐一对比）：

      20 张随机的 0/1 权图，每张 12 个顶点、约 17 条边
      每张图都验证「从 0 到全部 12 个顶点」的最短代价（与暴力枚举对比）：
        共验证 240 组，代价不一致的个数 = 0

240 组全部一致 ✓（和 12.3 节验证 BFS 时用的是同一套手法：用暴力枚举做独立校验，而不是"自己验证自己"）

0-1 BFS 是本节最该记住的一座桥：

容器	能表达的代价	算法
队列	所有边代价相同	BFS
双端队列	代价只有 0 和 1	0-1 BFS
优先队列	任意非负代价	Dijkstra（13.3）

三者是同一件事的三个档位 —— 每一次"换容器"，都是在把"能表达的代价种类"加宽。

13.3 节的 Dijkstra，就是把这个表格的第三行补完。

六、练习

练习 13.2.1（多源 BFS） 一个 4×4 的网格（顶点编号 $r \times 4 + c$，$r, c \in [0,3]$），有两个源点：0 和 15。 (a) 手工做多源 BFS，写出每个顶点的距离。 (b) 如果改成"对 0 跑一次、对 15 跑一次、再取最小"，结果一样吗？ (c) 多源 BFS 里，源点自己的距离是 0。如果题目问的是"到最近的其他配送站的距离"呢？

练习 13.2.2（判断） 判断对错并说明理由： (a) BFS 求出的路径一定是"总代价最小"的。 (b) 双向 BFS 一定比单向 BFS 快一个数量级。 (c) 多源 BFS 的复杂度和单源 BFS 一样，都是 $O(V+E)$。 (d) 0-1 BFS 用双端队列，是因为双端队列比普通队列快。

练习 13.2.3（为什么网格上只快 2 倍） 用本节第四节的推导： (a) 二维网格上，距离起点恰好 $k$ 步的顶点大约有多少个？（用 $k$ 表示） (b) 据此算出：单向 BFS 访问约多少个顶点？双向呢？ (c) 把结论推广：$m$ 维网格上双向 BFS 能快多少倍？ (d) 什么样的图，双向 BFS 才能获得"指数级"的提升？

练习 13.2.4（工程判断） 一个"外卖预计送达时间"的功能：路网有 50 万个路口，每条边记录通行耗时（秒）。 (a) 用 BFS 求"最快送达路径"，错在哪里？错得严重吗？ (b) 如果该公司想先做个"粗略版"，把每条边的耗时四舍五入成"通畅 / 拥堵"两种，分别赋值 1 和 2 秒 —— 这样能用 0-1 BFS 吗？ (c) 如果想把耗时量化成 0、1、2、3 四种值，还能用双端队列吗？该用什么？

七、练习答案

13.2.1

(a) 多源 BFS 的距离表

两个源点：0 和 15。编号规则 $r \times 4 + c$，所以 0 是左上角，15 是右下角。

推导要点：从 0 出发的距离是 $r + c$，从 15 出发的距离是 $(3-r) + (3-c)$，取较小者。

验证几个点：

• 顶点 5（$r=1, c=1$）：到 0 是 2，到 15 是 4 → 2 ✓
• 顶点 10（$r=2, c=2$）：到 0 是 4，到 15 是 2 → 2 ✓
• 顶点 3（$r=0, c=3$）：到 0 是 3，到 15 是 3 → 3（两个源点一样近）✓

(b) 一样。

因为多源 BFS 的 dist[v] 就是 $\min_s (\text{从 } s \text{ 到 } v \text{ 的距离})$ —— 这正是"每个源点各跑一次再取最小"的定义。

代价不同：多源 BFS 只跑 1 次 $O(V+E)$；两个源点各跑一次是 $2 \times O(V+E)$。源点越多，差距越大（本节实测 10 个源点是 10 倍）。

(c) 把源点自己也当成"要算的目标"就行不通了。

因为多源 BFS 里 dist[源点] = 0 —— 它算的是"到最近源点的距离"，而源点到自己当然是 0。

要算"到最近的其他配送站"，有两种做法：

第二种做法就是"多源 BFS 求最近点对" —— 它是解决这类问题的通用套路：不只是算距离，还要记录"是谁的地盘"。

13.2.2

(d) 是本节最容易搞反的一条 —— 换容器的理由是"要让容器能表达更多的代价种类"，不是"容器更快"。

BFS 用 Queue、0-1 BFS 用 Deque、Dijkstra 用 PriorityQueue —— 每一步换的都是"表达力"，性能是顺带的代价。

13.2.3

(a) 距离恰好 $k$ 步的顶点约 $4k$ 个。

推导：在无穷大的二维网格上，曼哈顿距离恰好为 $k$ 的点构成一个"菱形边框"，顶点数是 $4k$（$k=0$ 时是 1）。

验证：$k=1$ 有 4 个（上下左右）✓，$k=2$ 有 8 个 ✓，$k=3$ 有 12 个 ✓

(b) 单向和双向的访问量：

单向 BFS（半径 $d$）：

$$\sum_{k=0}^{d} 4k \approx 4 \cdot \frac{d^2}{2} = 2d^2$$

双向 BFS（各扩展 $d/2$，两份）：

$$2 \times \sum_{k=0}^{d/2} 4k \approx 2 \times 2\left(\frac{d}{2}\right)^2 = d^2$$

比值：$\dfrac{2d^2}{d^2} = 2$

所以二维网格上双向 BFS 就是快约 2 倍 —— 实测 2.14 倍（略有出入是因为网格有边界，且目标恰好落在第 $d$ 层）。

(c) $m$ 维网格上，快 $2^{m-1}$ 倍。

推导：$m$ 维网格中，距离 $k$ 的"球面"大小是 $O(k^{m-1})$，所以半径 $d$ 的球体积是 $O(d^m)$。

• 单向：$O(d^m)$
• 双向：$2 \times O((d/2)^m) = O(d^m / 2^{m-1})$
• 比值：$2^{m-1}$

有意思的是 $m=1$：在一条链上，双向 BFS 一点便宜都占不到 —— 因为链每层只有 1 个顶点，两个方向各走一半，访问总数和单向一样。

(d) 只有"每层顶点数随深度指数增长"的图，双向 BFS 才有指数级提升。

具体来说：

• 高分支树 / 状态图：社交网络（每人几百个好友）、魔方（每个状态十几个后继）、华容道、八数码
• 判别方法：问自己"从起点往外走 $k$ 步，能到达多少个不同的顶点" —— 如果这个数随 $k$ 指数增长，双向 BFS 有奇效；如果只是多项式增长，就别指望数量级的提升

13.2.4

(a) 错得很严重。

BFS 会把"经过路口数最少"当成"最快" —— 而一条走 3 个路口的城市快速路，可能比走 1 个路口的拥堵主干道快得多。

错得有多严重？ 本节实验三 (A) 那个反例里，BFS 选的路径代价是最优解的 66 倍（200 : 3）。真实路网上一般不会这么夸张，但"绕远走高速反而更快"是每天都会发生的事。

正确做法：用 Dijkstra（13.3 节）—— 边权就是通行耗时。

(b) 不能直接套用，但可以转化。

0-1 BFS 要求代价恰好是 0 和 1。 把"通畅 = 1、拥堵 = 2"直接喂进去是不行的。

转化方法：把所有边的代价都减 1 —— "通畅 = 0、拥堵 = 1"。

但要小心两点：

更稳妥的答案是：这个"粗略版"直接用 Dijkstra 就行 —— 13.3 节会看到，优先队列版 Dijkstra 的代码并不比 0-1 BFS 复杂多少，而且不用为代价的取值范围操心。

0-1 BFS 的价值在于"能省掉优先队列 $\log$ 的开销"，而不是"能处理更多情况"。

(c) 不能，双端队列只有两个"档位"。

四种代价值意味着需要"四档优先级" —— 双端队列表达不了。

该用优先队列（也就是 Dijkstra，13.3 节）。

这道题想说明的是一件事：容器的表达力决定了它能处理的问题。

代价种类的数量：1 种 → 队列；2 种 → 双端队列；任意多种 → 优先队列。

每加宽一档，容器的操作代价就上升一档（$O(1)$ → $O(1)$ → $O(\log n)$）—— 这是本书里"用一个更贵的容器换更强的能力"的又一个例子（6.2 节的开放寻址、10.4 节的平衡树是同一主题）。

八、常见错误

九、本节总结

1. "最短路径"必须先说清"最短什么"：BFS 最短的是边数，Dijkstra 最短的是边权和（13.3）。度量衡一变，BFS 的正确性就不再成立。
2. 多源 BFS = 把所有源点一起入队，一行代码的事。实测 10 个源点时快 10.0 倍，结果与"各跑一次取最小"完全一致。
3. 双向 BFS 的收益完全取决于图的形状 —— 这是本节的核心反预期：
   • 二维网格（每层 $4k$ 个）：2.14 倍
   • 3 叉树（每层 $3^k$ 个）：695.6 倍
   • 规律：每层顶点数随深度指数增长 → 指数级提升；多项式增长 → 常数倍提升（$m$ 维网格是 $2^{m-1}$ 倍）
4. 12.3 节那个"400 万倍"缺了前提 —— 它假设图是一棵理想多叉树。这也解释了地图导航为什么主力是 A* 而不是双向 BFS。
5. BFS 失效的信号：边上带了代价。 实测反例：BFS 选出代价 200 的路径，而最优是 3。
6. 0-1 BFS 是通往 Dijkstra 的桥：队列 → 双端队列 → 优先队列，每一步加宽"能表达的代价种类"。实测 240 组与暴力枚举完全一致。
7. 换容器是为了表达力，不是为了速度 —— 这是本节反复出现的一条判断标准。

下一节衔接：本节把 BFS 的边界划清楚了 —— 它管不了"带权图"。而现实中的图几乎都带权：距离、耗时、费用。

但 BFS 的那些零件一个都没浪费：dist 数组还在，prev 还在，一层层扩展的思路还在。下一节要换掉的只有一样东西 —— 队列。

13.1 节已经演示过这件事有多有效（Kahn 换个容器就换个顺序）；这一次，换个容器换来的是"能处理任意非负边权"。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "13.2",
  "title": "无权最短路：BFS 的正确用法",
  "covered": [
    "「最短路径」的三种度量衡与三种算法的对应（BFS / Dijkstra / Bellman-Ford）",
    "多源 BFS 的实现（所有源点一起入队）与虚拟源点的等价解释",
    "多源 BFS 实测：10 个源点时快 10.0 倍，结果与「各跑一次取最小」完全一致",
    "双向 BFS 的实现（每次扩展层数较少的一边、Expand 里先取 count、碰面判定）",
    "反预期实测：双向 BFS 在二维网格上只快 2.14 倍，在 3 叉树上快 695.6 倍",
    "「每层顶点数指数增长 vs 多项式增长」的解释与 m 维网格的 2^(m-1) 推广",
    "带权图上 BFS 失效的实测反例（代价 200 的 2 步路径 vs 代价 3 的 3 步路径）",
    "0-1 BFS（双端队列）的实现与 240 组暴力枚举验证",
    "「队列 → 双端队列 → 优先队列」是表达力的三个档位"
  ],
  "unresolved": [
    "Dijkstra 留到 13.3",
    "Bellman-Ford 与负权边留到 13.4",
    "A* 启发式搜索超出本书范围"
  ],
  "canonical_terms": {
    "最短路径（Shortest Path）": "从起点到终点的所有路径里，按给定度量衡最划算的那一条；无权图上即边数最少",
    "多源 BFS": "把所有源点一起入队、距离初始化为 0 的 BFS，一次求出到最近源点的距离",
    "双向 BFS": "从起点和终点同时扩展、每次扩展层数较少的一边，直到碰面",
    "0-1 BFS": "边权只有 0 和 1 时，用双端队列替代队列的最短路算法（0 权插队首，1 权插队尾）"
  },
  "symbols_units": {
    "V": "顶点数",
    "E": "边数",
    "b": "每个顶点的平均分支数",
    "d": "起点到终点的距离",
    "m": "网格的维度"
  },
  "assumptions": [
    "读者已掌握 12.3 的 BFS、dist/prev 数组与层序遍历",
    "读者理解 5.2 的队列与双端队列",
    "本节的性能度量一律是「访问顶点数」，与机器无关"
  ],
  "word_count_actual": 3651,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch13/Sec132/",
    "多源 BFS（90,000 vs 900,000，10.0 倍）与「距离数组完全一致」为实测",
    "双向 BFS 网格图 81,003 vs 37,801（2.14 倍）、树状图 797,161 vs 1,146（695.6 倍）为实测",
    "两处双向 BFS 的距离都与单向 BFS 结果一致（True）为实测",
    "带权反例（BFS 给 S->A->T 代价 200，最优 S->B->C->T 代价 3）为实测，最优解由暴力枚举独立验证",
    "0-1 BFS 与暴力枚举对比 20 张图 × 12 个目标 = 240 组，不一致 0 个，为实测",
    "本节全部指标是确定性的（访问顶点数 + 固定 seed），任何机器复现结果相同",
    "术语写法与 glossary.md 一致（最短路径、广度优先搜索、层、前驱数组）"
  ],
  "known_issues": [
    "初版把 0-1 BFS 的验证图设成 60 个顶点、180 条边，暴力枚举所有简单路径直接组合爆炸，程序跑满 5 分钟没结束（被强制中断）——改为 20 张 12 顶点的稀疏图，共 240 组，与 12.3 节验证规模一致",
    "初版单源 BFS 用的是「跑完整个连通分量」的版本，与「找到目标就停」的双向 BFS 对比不公平（网格上 250,000 vs 40,000，虚高了 3 倍）——增加了 BfsToTarget 专门用于对比",
    "树状图上单向 BFS 访问了全树 797,161 个顶点，起初以为算错了；实际是因为 visited 在【入队】时计数，而处理深度 11 层时会把深度 12 层的 531,441 个节点全部入队。正文明确「访问 = 入队」的口径",
    "初版代码在 C# 字符串里嵌了英文双引号（\"沿周长\"），会导致字符串提前截断、编译失败——中文正文里一律改用「」"
  ],
  "next": "13.3 Dijkstra 算法"
}