0-1 bfs 学习笔记

01 bfs 是一种可以在 \(\mathcal{O}(n + m)\) 时间求解只含有 \(0\)，\(1\) 两种边权的单源最短路的算法。这种情形下效率比 dijkstra 更高，和 dijkstra 一样好写（甚至更好写一点）。

我们知道边权仅为 \(1\) 的最短路（可以看做无权图最短路）可以通过纯 bfs 使用 \(\mathcal{O}(n + m)\) 解决，而 dijkstra 是 \(\mathcal{O}((m+n) \log n)\) 的，我从这里引入。

dijkstra 之所以有个 \(\log n\) 就是因为取距离最小的点时存在瓶颈，那么为什么 bfs 只需要取队头呢？因为有了边权仅为 \(1\) 的特性，因此无论什么时候，队头到队尾，对应的距离都是单调不降的。

为了方便叙述，我们将 bfs 中队列里的每个元素（代表节点编号）\(u\) 都替换为 \(d_u\) 后的序列记作 \(q\)，\(q\) 的开头对应原队列开头。

比如 bfs 中队列 \((2, 4, 3)\)，那么我们的 \(q\) 会表示为 \((d_2, d_4, d_3)\)。因图而异，这个 \(q\) 可能是 \((0, 1, 1)\)，也有可能是 \((2, 3, 3)\)……

在无权图最短路中我们每次只会把 \(q\) 的开头 \(D\) pop 掉，然后把若干个（可能没有）\(D + 1\) push 到队列的尾部，那么显然当 \(q\) 初始为 \((0)\) 时，这样操作一定可以恒定使得 \(q\) 单调不降，并且事实上，任何时刻上 \(q\) 一定可以表示成 \(D, D, \cdots, D,D+1, D+1, \cdots, D+1\) 的形式，也就是先一段 \(D\) 后一段 \(D+1\) 的形式（可以全都是 \(D\) 或 \(D +1\)）。不信你试试看。

但是在 0-1 bfs 中，我们把 \(D\) pop 掉之后，push 进去的点有两种情况：\(D\) 和 \(D+1\)。如果我们直接 push 到尾部会破坏单调性。会出现类似于 \(D, D, D + 1, D, D + 1\) 这种支离破碎的情况……怎么办呢？

01 bfs 的精髓就来了：

• 把队头 \(u\) 弹出，遍历 \(u\) 连向的所有节点 \(v\)（\(D = d_u\)）；
• 尝试松弛 \(v\)，如果成功：
  • 如果 \(u \to v\) 边权为 \(1\)，那么把 \(v\) push 到队尾（把 \(D + 1\) 放到 \(q\) 的尾部）；
  • 如果 \(u \to v\) 边权为 \(0\)，那么把 \(v\) push 到队头（把 \(D\) 放在 \(q\) 的头部）。

这样处理后 \(q\) 仍然可以时刻表示成 \(D, D, \cdots, D,D+1, D+1, \cdots, D+1\) 的形式。原因也是显然的。

另外，为了保证 dijkstra 每个点只会入队和出队一次，我们需要 vis 数组和松弛操作并用；

（其实不写 vis 数组也能过但是常数会比较大，因为每个点会入队多次出队多次，多余的点会尝试松弛它的出点，虽然显然所有松弛都是失败的，可以认为是进行了一次没用的循环。当然还有个东西叫懒惰删除~不是 vis 数组胜似 vis 数组的效果。懒惰删除会让一个点入队多次出队多次，但是只有一个点的第一次出队才会进行松弛操作，剩下多余的直接弹，所以更几乎不影响时间复杂度）。

而无权最短路 bfs 可以把 vis 数组和松弛操作随便丢一个。。

这个想想就知道，无权 bfs 是一层一层往下推，节点 \(u\) 第一次被搜索到的深度就是它的最短路，因此后面再访问 \(u\) 不再需要进行任何操作。

但是 0-1 bfs，我们举个例子：\(1 \to 2 \to 3 \to 4 \to 5 \to 6\)，每条边都是 \(0\) 是比一条边权为 \(1\) 的 \(1 \to 6\) 更优的。但是我们会先从 \(1\) 拓展到 \(2\) 和 \(6\)，\(d_6\) 会先被写上 \(1\)（假的），后面才能从 \(5\) 搜索到 \(6\) 从而使 \(d_6 = 0\)，这个操作显然是需要松弛的。所以松弛不能丢。

但是 0-1 bfs 直接丢掉 vis 数组是可以的。我们假设当前节点为 \(u\)，正在遍历出边 \((u, v, w \in \{0, 1\})\)：

• 当 \(w = 0\) 时显然 \(d_v = d_u\) 就是 \(v\) 确定的最短路了；
• 当 \(w = 1\) 时，\(d_v\) 会被标记成 \(d_u + 1\)，那么 \(d_v\) 实际的最短路可能是 \(d_u + 1\) 也有可能是 \(d_u\)（显然只有这两种情况），因此 \(v\) 后面可能又会被重新松弛为 \(d_v\) 一次，而且也就最多这一次了。

所以一个点最多被入队两次，时间复杂度可以接受。所以不需要 vis 数组~

由于 0-1 bfs 中需要给队列的两端 push，需要使用到双端队列，因此也叫双端队列 bfs 和 dqbfs（？）

代码就不上了。