0-1广度优先搜索

定义

0-1广度优先搜索是一类在边权仅为0或1的图上求单源最短路径的算法，其名称来自边权的两种取值。给定一个含 $V$ 个顶点、$E$ 条边的带权图，以及一个源点，算法要求算出源点到其余各个顶点的最小路径代价，而路径代价是沿途边权之和^[2]。在无权图上，普通广度优先搜索可以在 $O(|E|)$ 时间内完成同一任务，等价于所有边权都为1的情形；当边权只扩展到0和1两种取值时，问题仍能在不引入优先队列的前提下线性求解，这就是0-1 BFS的处理对象^[2]。

原理

算法的基本框架沿袭迪杰斯特拉算法：维护数组 $d$ 记录源点到各顶点的当前最短估计，初始时源点为0、其余为正无穷，反复取出一个尚未确定的顶点并对其出边做松弛操作，即若 $d[u] > d[v] + w$ 则更新 $d[u]$^[2]。区别在于待处理顶点的组织方式。由于边权只有0和1，队列中任意顶点到源点的距离与当前处理顶点的距离最多相差1，队列内容始终呈「距离为 $d$ 的一段、距离为 $d+1$ 的一段」的形态。因此无需平衡树或堆，只需一个双端队列：权值为0的边产生的新顶点压入队首，权值为1的边产生的新顶点压入队尾，队列便始终保持按距离升序排列^[2]。

取出队首顶点 $v$，对其每条出边 $(v,u)$ 尝试松弛：若 $d[v]+w<d[u]$，则令 $d[u]=d[v]+w$；当 $w=0$ 时将 $u$ 压入队首，否则压入队尾。重复该过程直至队列为空，得到的 $d$ 即为各点的最短距离。因为每个顶点可能因距离被多次改小而重复入队，实现中通常需要在出队时判断该记录是否过期^[4]。

step 1 d[s] = 0, 其余为 ∞, 双端队列置入 s

step 2 取出队首 v, 遍历出边 (v,u,w)

step 3 若 d[v]+w < d[u]: 更新 d[u]

w = 0 → u 压入队首

w = 1 → u 压入队尾

step 4 队列非空则返回 step 2

flowchart TD

A[初始化 d[s]=0, 队列置入 s] --> B{队列是否为空}

B -- 否 --> C[取出队首顶点 v]

C --> D[遍历 v 的出边 u, 权值 w]

D --> E{是否可松弛}

E -- 否 --> B

E -- 是 --> F[w 为 0]

E -- 是 --> G[w 为 1]

F --> H[u 压入队首]

G --> I[u 压入队尾]

H --> B

I --> B

B -- 是 --> J[输出各点最短距离]

发展历程

0-1 BFS 的思路由迪杰斯特拉算法的队列行为推导而来：在该算法中，若只允许0和1两种边权，则每轮入队顶点的距离只可能是当前距离或当前距离加一，优先队列的最小值弹出性质可以由双端队列的两端插入直接复现^[2]。这一观察使算法在竞赛编程社区中广泛流传，2015年12月有作者在Codeforces讨论区发布了系统性讲解，给出「BFS 队列中最多同时含相邻两层顶点」的引理，并据此说明两端插入为何能维持有序^[5]。此后各类算法教程站点与在线判题平台的开源算法资料，都将0-1 BFS列为无权 BFS 与迪杰斯特拉算法之间的中间形态，并把权值上界推广的情形归入 Dial 算法^[2]。

应用

该算法适用于代价只有两种可能、且其中一种不产生代价的建模场景。公共交通换乘是常见类比：站内步行换乘不增加购票次数，可记为权值0，乘坐一段新线路需再购票一次，记为权值1，求最少购票次数即对应0-1 BFS 的最短路问题^[4]。有资料把同类结构用于公共交通网络导航、编辑距离计算与生物系统建模等领域^[1]。

在题目转化层面，带方向的边可以拆成一条权值0的原边和一条权值1的反向边，从而把「最少反转多少条边」一类问题化为0-1 图上的最短路^[6]。网格题中同样可用这一手法：沿允许方向前进记为0，其余方向的移动记为1，再用0-1 BFS 求出走到目标格的最小代价^[6]。

局限

算法的正确性与线性复杂度都依赖边权只能取0和1这一前提。若边权出现其他取值，两端插入无法再维持队列按距离有序，需改用优先队列或其他结构^[6]。即便边权只有两种但取值不是0和1，也有讨论指出不能直接套用该做法，因为队列的有序性不再由两端插入保证^[6]。

当边权上限扩大为不超过 $k$ 的整数时，队列中顶点距离的跨度也随之扩大到 $k$，此时需维护 $k+1$ 个桶并在最小桶取空后循环移位，这种方法称为 Dial 算法，是0-1 BFS 的推广而非其本身^[2]。此外，0-1 BFS 只是求解单源最短路径，不涉及负权边情形；路径数量、次短路等额外需求也不在其处理范围内^[2]。

参见

• 广度优先搜索 —— 0-1 BFS 由它扩展而来，处理边权不再全为1的情形。

• 迪杰斯特拉算法 —— 通用非负权单源最短路算法，0-1 BFS 可视为其在0、1边权下的特化。

• 双端队列 —— 支撑队首、队尾两端插入的核心数据结构。

• 图论 —— 该算法所属的学科领域。

• 最短路径 —— 算法所求解的问题类型。