0–1 BFS | Codeboy's Blog

一次操作免费，另一次操作收费一单位。例如地图中的普通移动免费，穿过一个障碍收费一；要最小化的便是障碍数，而不是走过的边数。普通BFS按边数分层，此时不再适用；但也不必立即换成对数时间的堆，因为下一条边只可能让距离不变或增加一。

形式陈述

输入、输出与结算规则

给定有限邻接表图、源点 $s$ ，每条边权属于 $\{0,1\}$ 。图可以有向；无向边按两个方向各存一条。输出从源点到所有顶点的最短距离，以及用于恢复一条最短路的父边；不可达点距离为 $+\infty$ ，父边为空。

0–1 BFS 是Dijkstra 算法在零一权重上的专用实现：仍然每次结算最小暂定距离，只是用双端队列完成最小键选择。队列每项保存入队时距离快照与顶点 $(d,u)$ ，而不是把可变的 dist[u] 当作旧项不可变的键。

从有效项 $(d,u)$ 松弛出边 $u\to v$ ，若 $d+w<\operatorname{dist}[v]$ ，更新距离与父边。 $w=0$ 的新项放队头， $w=1$ 的新项放队尾。弹出后若快照与当前距离不符，则跳过，不重新扫描出边。必须严格改进才入队，零权圈上的相等距离不能反复加入。

最小实现

下面假设输入已满足顶点范围、非空源点与零一边权约定；完整核验程序包含逐边输入检查与路径重建。

python

from collections import deque
from math import inf

def zero_one_bfs(adj, source):
    dist = [inf] * len(adj)
    parent = [None] * len(adj)
    dist[source] = 0
    queue = deque([(0, source)])
    while queue:
        value, u = queue.popleft()
        if value != dist[u]:
            continue
        for v, weight in adj[u]:
            candidate = value + weight
            if candidate < dist[v]:
                dist[v] = candidate
                parent[v] = (u, weight)
                if weight == 0:
                    queue.appendleft((candidate, v))
                else:
                    queue.append((candidate, v))
    return dist, parent

parent[v] 保存前驱与实际边权，便于核验平行边下的路径费用。源点的父边一直为空；重建时先处理 target==source 的零边路径，不能因此把源点误判为不可达。

直觉

队列只需要两个相邻距离层

归纳维护队列快照按非降序排列，且队头键若为 $d$ ，其余键只能是 $d$ 或 $d+1$ 。初始只有零，结论成立。从队头取出有效项后，零权松弛生成键 $d$ ，放在前端仍不大于现有项；一权松弛生成键 $d+1$ ，放在后端仍不小于现有项。

弹出旧项时不生成新记录，删除本身不会破坏排序。若较小的一层已空，队头升到下一层；之后新的候选又只比这个新队头大零或一。因而每次实际扩展的顶点都持有全体候选中的最小键，可以直接使用Dijkstra的非负权结算证明。

这里排序的是保存的快照。假如队尾旧项写着 (1,a)，后来队头加入 (0,a)，当前 dist[a] 已为零；不能据此把队尾旧项也读成键零，再声称整列顶点的“当前距离”有序。数据结构维护的对象和程序外部数组中的值必须分开。

为什么不用首次访问标记

普通BFS第一次发现顶点时距离已经最优，0–1 BFS则要等到第一次有效弹出。图有 $s\to a:1,s\to b:0,b\to a:0$ 时，先扫描 $s\to a$ 会发现费用一，但经过 $b$ 后能降成零。若在入队时把 a 永久标成已访问，就会拒绝这个改进。

有效弹出后不用再显式重开顶点。非负权与最小键顺序保证这次距离已经最短，以后的边不可能严格降低它。零权平局允许任意结算次序，因为所有这些顶点已在同一最短距离层上。

例子与边界

带两份旧项的完整执行

取顶点 $s,a,b,c,t,z$ ，其中 z 孤立；边为

s\to a:1,\ s\to b:0,\ b\to a:0,\ b\to c:1,\ a\to c:0,\ c\to t:1.

按上面的邻接顺序扫描，队列变化如下。表内每项是“快照距离，顶点”。

刚完成的操作	队列从头到尾
扩展 s	(0,b), (1,a)
扩展 b	(0,a), (1,a), (1,c)
扩展 a	(0,c), (1,a), (1,c)
扩展 c	(1,a), (1,c), (1,t)
丢弃旧 a、旧 c	(1,t)
扩展 t	空

最后距离为 $(0,0,0,0,1,+\infty)$ 。父边恢复 $s\to b\to a\to c\to t$ ，费用 $0+0+0+1=1$ 。旧 a 与旧 c 虽然各多弹出一次，但都不重复扫描出边；总共仍只扫描六条可达出边。

若只查询 t，可以在 t 的有效项弹出时停止，不能在第一次松弛到 t 时停止。例如 $s\to t:1,s\to b:0,b\to t:0$ ，发现 t 的第一次费用一仍可能被改进。

权重只出现两种值，不一定足够

边权属于 $\{0,x\}$ 且 $x>0$ 时，先把所有权除以 x，得到零一问题；最短路径不变，最后距离乘回 x。 $x=0$ 时所有可达点距离为零，直接按零权规则遍历即可。

边权若是 $\{x,x+1\}$ ，一般不能减去 x 变成零一权，因为一条含 k 条边的路径会被减去 kx，不同边数的路径受到不同修正。例如原图中两条权二的边构成费用四的路线，另一条权三的边构成费用三的路线；减二后前者变成零，后者变成一，优劣颠倒。任意负权、非整数近似值也不满足本页接口。

推论与应用

时间线性，快照空间也能保持线性

以下时间界按单位成本RAM计：顶点下标、有限距离及中间距离和须装入可操作的机器字，加法、比较和所用队列基本操作按各自已声明成本收费。若权重或累计费用是任意长整数，须另计其位运算成本；这与radix heap页对Word-RAM及最高置位指令的要求相衔接。

每个顶点至多有效扩展一次，每条可达出边因此至多扫描一次。每次成功松弛生成一个记录，总数先可保守界为 $m+1$ ；每条记录入队和弹出各一次，故时间为 $O(n+m)$ ，其中 n 项距离与父边初始化不能省略。

零一权还给出更强的记录数界。设顶点第一次被发现时，当前正在扩展的距离为 d，则它第一次暂定值只能是 d 或 d+1。后续扩展距离不小于 d；所以若还能严格改进，只可能从 d+1 改成 d，之后不再变化。每个非源点至多两次入队，源点一次，队列与距离、父边合计占 $O(n)$ 辅助空间。这里的“两次”依赖整数零一权，不能搬到一般惰性Dijkstra。

从两个距离层推广到有限窗口

如果边权是 $0,1,\ldots,C$ ，候选窗口会扩成 C+1 个距离值。Dial 算法用环形桶代替一个deque，保持相同的最小键结算语义；C 很大时逐个跳过空距离可能昂贵，再考虑radix heap按二进制差异压缩距离范围。

手算终点不只是得到距离一：还应指出上表哪两项已经过时，解释为什么不能第一次发现就锁定，并从父边逐项加出路径费用。换成收费地形地图时，先说明边权计的是“进入目标格”还是“离开源格”；两种建模会影响起点是否收费，算法不会替应用补上这个约定。

参考资料

Peter Sanders, Kurt Mehlhorn, Martin Dietzfelbinger and Roman Dementiev, Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox, Ch.10, Springer, 2019，§10.5.1：非负整数权Dijkstra的有限键窗口与桶队列；零一权是窗口宽一的情形。
Jiacheng Ye, Computing Exact Bottleneck Distance on Random Point Sets, Virginia Tech硕士论文, 2020，§4.3.2、Algorithm6，pp28–29：0/1 BFS在匹配算法中的实现应用。本文使用距离快照与旧项跳过，并单独证明队列与记录数界。

形式陈述 ​

输入、输出与结算规则 ​

最小实现 ​

队列只需要两个相邻距离层 ​

为什么不用首次访问标记 ​

带两份旧项的完整执行 ​

权重只出现两种值，不一定足够 ​

时间线性，快照空间也能保持线性 ​

从两个距离层推广到有限窗口 ​

反向链接