算法与数据结构 · 第 31 课
Dinic:为什么一次 BFS 可以处理多条最短增广路?
2026 年 11 月 19 日|第 5 周 · 第 3 天|讲授约 17 分钟(自测另计)
昨天的 Edmonds–Karp 每找到一条最短增广路,就重新进行一次 BFS。今天只改变组织方式:同一轮 BFS 算好层次后,连续沿层次递增的边送流,直到所有这一长度的增广路都被堵住。 这就是 Dinic 的“层次图 + 阻塞流”。
一、学习目标和前提(约 1 分钟)
完成本课应能:①解释层次图与阻塞流,特别分清“堵住路径”和“把所有边填满”;②手工执行 Dinic 的两轮 BFS 与多次 DFS 推流;③写出当前弧优化的正确用法;④证明最短增广路长度逐阶段严格增长;⑤推导一般网络 O(n²m) 时间、O(n+m) 工作空间。
| 设有向容量网络有 n= | V | 个顶点、m= | E | 条原始边,s≠t,容量是非负有限数。理论上用精确算术,不要求容量为整数。每条原始边都建立带索引的正反残量弧:正向剩余容量 c−f,反向撤销容量 f。 |
二、BFS 只负责分层,不决定一条特定路径(约 2 分钟)
在当前残量网络上,从 s 沿正残量弧运行 BFS,记 level[v] 为到 v 的最少边数(不可达记 −1)。只保留满足以下两个条件的残量弧:
[ r(u,v)>0,\qquad level[v]=level[u]+1. ]
得到的子图叫层次图(level graph)。每条保留弧都使层数加 1,因此它没有有向环;其中任何 s→t 路径都恰好使用 level[t] 条边,也就是本轮最短增广路。请注意:某条反向残量弧如果恰好指向下一层,也可以出现在层次图中;不能一概禁止反向弧。
下面继续使用上一课的五边网络(括号内是容量),方便比较两种算法。
flowchart LR
S((s)) -->|"3"| A((a))
S -->|"2"| B((b))
A -->|"2"| T((t))
A -->|"1"| B
B -->|"3"| T
第一轮 BFS 给出:
[ level[s]=0,\quad level[a]=level[b]=1,\quad level[t]=2. ]
因此 s→a、s→b、a→t、b→t 属于本轮层次图,a→b 不属于:它连接两个同为第 1 层的点。层次图只包含当前最短路径可能使用的边,并非把原始图永久删边。
三、阻塞流:堵住每条当前最短路径(约 2 分钟)
阻塞流(blocking flow) 是在当前层次图中增加的一组合法流,使得增加后该层次图中不再存在从 s 到 t 的正残量路径。等价地说,原本每一条层次图 s→t 路径都至少有一条边被饱和。
这不等于每条边都饱和,也不等于完整残量网络已经没有更长的增广路径。阻塞的对象只是当前 BFS 所确定的最短长度。
Edmonds–Karp 的做法是“BFS → 一条路 → BFS”;Dinic 是“BFS → 多次只沿层次递增边 DFS → 阻塞后再 BFS”。一轮 BFS 可以消除多条同长度的增广路。
四、完整数值 Trace:两次 BFS,三次推流(约 3 分钟)
层次 0→1→2,有两条长度为 2 的可行路线。
| 阶段内推流 | 本轮允许的路径 | 瓶颈 Δ | 累积流值 |
|---|---|---|---|
| 第 1 次 | s→a→t | 2 | 2 |
| 第 2 次 | s→b→t | 2 | 4 |
此时 a→t 和 s→b 都已饱和,原层次图再无 s→t 路径;第一阶段阻塞流值为 4。虽然 a→b(1) 仍未使用,但它是同层边,不能在本阶段使用。
重新计算残量:s→a 还剩 1,a→b 还剩 1,b→t 还剩 1。BFS 此时给出:
[ level[s]=0,\quad level[a]=1,\quad level[b]=2,\quad level[t]=3. ]
| 阶段内推流 | 新最短路径 | 瓶颈 Δ | 累积流值 |
|---|---|---|---|
| 第 3 次 | s→a→b→t | 1 | 5 |
此后源点的两条出边均饱和,第三次 BFS 到不了 t,算法停止。源点侧可达集合为 ({s}),其割容量是 3+2=5,与流值相等,因而已经最大。全程 BFS 最短 s→t 边数从 2 变成 3,最后变成不可达。
flowchart LR
P1["第 1 阶段:BFS 距离 2"] --> F1["DFS 送 2 + 2,阻塞当前层次图"]
F1 --> P2["第 2 阶段:BFS 距离 3"]
P2 --> F2["DFS 再送 1,阻塞"]
F2 --> Stop["下一次 BFS:t 不可达;最大流 5"]
五、算法伪代码:当前弧指针避免重复试错(约 3 分钟)
DINIC(G,s,t):
为每条原始边建立独立的 forward/reverse 残量弧配对
total = 0
while BFS_LEVEL(s, 仅沿 cap>0 的残量弧):
if level[t] == -1: break
ptr[u] = 0 for every u # 每轮重置
while (p = DFS_PUSH(s, +INF)) > 0:
total += p
return total
DFS_PUSH(u, limit):
if u == t: return limit
while ptr[u] < len(adj[u]):
a = adj[u][ptr[u]]
v = a.to
if a.cap > 0 and level[v] == level[u]+1:
p = DFS_PUSH(v, min(limit, a.cap))
if p > 0:
a.cap -= p
reverse(a).cap += p
return p # 有剩余时,下次可继续尝试此弧
ptr[u] += 1 # 当前弧无用,才跳下一条
return 0
BFS 需要把全部可达点的层次建好;伪代码里的 BFS_LEVEL 返回层次信息,外层据 level[t] 判断是否继续。只使用正残量弧,避免容量为 0 时无意义递归。
当前弧(current arc)不变量: 在同一阶段中,ptr[u] 之前的出弧已经被证明不可能继续产生有效的层次递增推流;它们无需反复扫描。只有尝试失败才前进 ptr[u],成功推流后保留当前索引,以免错误跳过尚有剩余容量的弧。下一轮 BFS 必须重置所有指针,因为层次关系可能改变。
每次沿残量路径推流都保持容量约束和流守恒;正向残量减少、配对反向残量增加,所以允许撤销以前的决策。层次严格递增意味着 DFS 不会在当前层次图中陷入有向环。
六、正确性:为什么阶段结束后最短距离严格增大?(约 3 分钟)
首先,在任意一轮 BFS 建好的层次图中,所有可用弧都使旧层数加 1。一次 DFS 推流后,可能新增正残量的弧只能是所走层次弧的反向弧;这些新弧从旧的第 i+1 层指回第 i 层,不可能帮助构造更短的正向 s→t 路线。旧有其他残量弧本来就满足 BFS 三角不等式,因而任何顶点的残量最短距离不会下降。
更严格地,假设下一次 BFS 仍找到长度不超过旧的 L=level[t] 的 s→t 路径。它每一步都必须使旧层数增加 1,才能在最多 L 步到达旧第 L 层的 t;因此整条路径只能使用旧层次图里的递增弧。但阻塞流已经使所有这样的 s→t 路径至少有一条弧饱和,而新出现的反向弧又是降层弧,不可能补上这条路径。矛盾。
所以每完成一个阻塞流阶段,如果 t 仍可达,就有
[ \boxed{level_{\mathrm{next}}[t] > level_{\mathrm{old}}[t].} ]
一条最短简单路径最多有 n−1 条边,因此有效阶段至多 n−1 个。最终 BFS 无法到达 t 时,由上一课最大流–最小割证明,当前流即最大流;Dinic 只是更聪明地组织合法的残量增广,并未改变最大流正确性条件。
七、为什么总时间 O(n²m)?(约 2 分钟)
单阶段 BFS 需要 O(n+m)。利用当前弧指针,所有顶点的指针在同一阶段合计最多越过 O(m) 条残量弧;每次成功的完整 s→t 推流至少会饱和一条层次弧,因此成功推流次数至多 O(m),而每次递归路径长度至多 n−1。于是构造一个阻塞流最坏 O(nm),整个算法至多 O(n) 个阶段:
[ \boxed{T_{\mathrm{Dinic}}=O(n^2m),\qquad S_{\mathrm{extra}}=O(n+m).} ]
这里假设常规邻接表、当前弧优化,并把初始化与 BFS 的 O(n+m) 成本计入;对通常存在源汇路径的情形,上述界包含这些工作。邻接表残量弧、层次数组、指针和 DFS 栈占 O(n+m) 空间。
对比 Edmonds–Karp 的 O(nm²):EK 每条最短增广路都重新 BFS;Dinic 在一次 BFS 后处理整个阻塞流。两个上界并不意味着任何具体输入 Dinic 都严格更快。非整数容量不破坏组合复杂度证明;浮点实现则必须谨慎处理正残量容差。原图的平行边或相反方向原始边,要分别保存边 ID 和对应的反向残量弧,不能错误合并。
八、小结与下一课(约 1 分钟)
[ \boxed{\text{BFS 分层} \to \text{DFS 求阻塞流} \to \text{最短增广路长度严格增长} \to O(n^2m).} ]
最容易犯的三个错误是:把阻塞流误解为填满全部边;把层次图当作永久修改原图;成功推流后错误地跳过仍有剩余容量的当前弧。
下一课(2026-11-20,第 32 课):二分图最大匹配与最大流归约。 从“每人最多匹配一个任务”构造容量为 1 的网络,证明整数最大流如何对应匹配,再解释 Hopcroft–Karp 为什么也使用 BFS 层次和一批增广路径。
参考资料:Dinic’s algorithm — cp-algorithms。
四级自测(总分 100;首次不公布答案)
前 3 题客观判分,第 4 题开放推导。仅提供中立提示;标准答案与解析放在独立测验 JSON 中。
Lv1|当前弧指针的作用|15 分|预计 2 分钟|单选
Dinic 的阻塞流 DFS 为每个顶点维护当前弧指针 ptr[u]。下列说法哪项正确?
A. 一旦某条边在第一轮 BFS 中被跳过,此后所有 BFS 轮次都不得再检查它。
B. 当前轮 DFS 证明一条候选弧无法继续推流时,可以将 ptr[u] 向后移动;重建 BFS 层次后应重新初始化指针。
C. 只有容量为整数时,当前弧指针才是正确的。
D. 只要沿某条弧成功推送过一次,就必须立即永久跳过它,即使它仍有正残量。
中立提示:区分“当前层次图中已失败”和“今后轮次永远无用”;再考虑部分推流后边可能仍有容量。
Lv2|分层与阻塞流数值 Trace|20 分|预计 4 分钟|单选
有向网络的原边及容量为 s→a(4)、s→b(3)、a→t(3)、a→b(2)、b→t(4),初始零流。第一轮 BFS 层次图中先沿 s→a→t 推流,再沿 s→b→t 推流,直到阻塞;第二轮重新 BFS 并继续到下一次阻塞。问 (第一轮结束的总流值,第二轮结束的总流值,第二轮开始时 level[t]) 是哪一组?
A. (6,6,2)
B. (6,7,3)
C. (7,7,2)
D. (5,7,3)
中立提示:先写出第一轮四个顶点的 BFS 层数,排除不符合“层数加一”的边;第二轮重新计算剩余容量与层次。
Lv3|阻塞流含义、阶段证明与边界|25 分|预计 4 分钟|多选
关于一般非负容量网络上的 Dinic(使用精确算术与正确的残量弧配对),下列哪些判断成立?(多选)
A. 阻塞流意味着当前层次图中的每一条边都被饱和。
B. 阻塞流只要求当前层次图不存在 s→t 正残量路径;完整残量网络中仍可能存在更长的增广路。
C. 完成一个阻塞流阶段后,如果下一次 BFS 仍能到达 t,那么 t 的最短残量路径边数严格增加。
D. Dinic 的一般 O(n²m) 时间界必须以容量为整数为前提。
中立提示:注意“堵住所有最短路径”不等于“填满所有边”;再分开判断组合复杂度与容量数值。
Lv4|算法设计、正确性与复杂度证明|40 分|预计 11 分钟|开放推导
给定 n≥2 个顶点、m 条有向边、非负有限容量的网络 G,源点 s≠t。(a)(12 分)写出 Dinic 的 BFS 分层、只沿 level[v]=level[u]+1 的正残量弧推流、当前弧指针和配对反向弧更新的伪代码。(b)(8 分)定义阻塞流,并用本课五边网络说明为什么第一轮要排除同层边 a→b,以及一轮为何可以连续送多条路径。(c)(12 分)证明一次阻塞流完成后,若 t 仍可达则其最短残量边数严格增长,进而界定阶段数。(d)(8 分)推导一般实现每阶段 O(nm)、总时间 O(n²m)、额外空间 O(n+m) 的界;比较 Edmonds–Karp,并说明非整数容量、零容量边、平行/反向原始边的处理。
中立提示:先证明 BFS 所有层次边都从第 i 层指向第 i+1 层,再跟踪增广新产生的反向弧;复杂度按指针前进次数和成功推流次数分别计数。
提交与反馈
请回复 Lv1:选项;Lv2:选项与两阶段 Trace;Lv3:全部正确选项;Lv4:(a)–(d) 证明与复杂度推导。我会按 15/20/25/40 分批改:80–100 分按原计划进入匹配;60–79 分补层次图与阻塞流练习;低于 60 分先复习残量弧、DFS 指针及最短路层数不变量。补练不修改自然日课号。