数据结构与算法 / 系统课时

Dinic 怎样加速最大流

Dinic 怎样加速最大流

最大流的难点不在“能不能找到一条增广路”,而在于如何减少重复搜索。Dinic 把残量网络分阶段处理:先用 BFS 建立分层图,再用 DFS 一次尽量推满这一层的可行流,从而显著减少无效增广。

学习目标

  • 理解分层图、可行边与阻塞流分别解决什么问题。
  • 能实现带当前弧优化的 Dinic,并验证最大流结果。
  • 知道 Dinic 的复杂度、适用范围和常见调试不变量。

为什么分层能减少无效搜索

任意增广算法都在残量网络上工作:一条边还有剩余容量时可以继续向前送流,已经送出的流又会通过反向边提供“撤销”空间。若每次只是随意找一条增广路,搜索容易反复经过已经证明无效的区域。

Dinic 每一轮先从源点做 BFS,记录每个点到源点的最短层数。之后只允许沿满足 level[v] = level[u] + 1 的残量边前进,这些边组成分层图。DFS 因而不会在同一轮里走回头路,也不会沿着更长的绕行路径尝试送流。

Dinic 一轮中从残量网络到分层图再到阻塞流的关系

一轮阻塞流完成后,当前分层图中已经不存在还能继续增广的源汇路径。若下一轮汇点仍可达,新的最短源汇距离会严格增加;若汇点已经不可达,当前流就是最大流。

阻塞流和当前弧优化

“阻塞”并不表示分层图里的所有边都饱和,而是表示每一条从源点到汇点的分层路径上,至少有一条边已经没有剩余容量。这样,本轮继续在旧分层图里搜索也不会再增加总流量。

实现时通常再维护 ptr[u],记录节点 u 下一条尚未彻底检查的邻接边。某条边已经满流、层级不合法,或递归后无法继续送流,就不必在同一轮里从头检查。这个当前弧优化对实际性能很重要。

实现一个可运行的 Dinic

下面使用邻接表保存残量边。每次加入容量为 c 的正向边,同时加入容量为 0 的反向边;推流时同时减少正向残量、增加反向残量。

python
from collections import deque
from dataclasses import dataclass

@dataclass
class Edge:
    to: int
    rev: int
    cap: int

class Dinic:
    def __init__(self, n: int):
        self.g = [[] for _ in range(n)]
        self.level = [-1] * n
        self.ptr = [0] * n

    def add_edge(self, u: int, v: int, cap: int) -> None:
        # rev 互相指向对方,更新残量时可以 O(1) 找到反向边。
        fwd = Edge(v, len(self.g[v]), cap)
        rev = Edge(u, len(self.g[u]), 0)
        self.g[u].append(fwd)
        self.g[v].append(rev)

    def bfs(self, s: int, t: int) -> bool:
        self.level = [-1] * len(self.g)
        self.level[s] = 0
        q = deque([s])

        while q:
            u = q.popleft()
            for e in self.g[u]:
                if e.cap > 0 and self.level[e.to] == -1:
                    self.level[e.to] = self.level[u] + 1
                    q.append(e.to)

        return self.level[t] != -1

    def dfs(self, u: int, t: int, pushed: int) -> int:
        if u == t or pushed == 0:
            return pushed

        while self.ptr[u] < len(self.g[u]):
            i = self.ptr[u]
            e = self.g[u][i]

            if e.cap > 0 and self.level[e.to] == self.level[u] + 1:
                flow = self.dfs(e.to, t, min(pushed, e.cap))
                if flow > 0:
                    # 正向减少、反向增加,始终保持合法残量网络。
                    e.cap -= flow
                    self.g[e.to][e.rev].cap += flow
                    return flow

            self.ptr[u] += 1

        return 0

    def max_flow(self, s: int, t: int) -> int:
        # 每次 BFS 固定一张分层图,内层 DFS 负责求这一层的阻塞流。
        total = 0
        inf = 10**18

        while self.bfs(s, t):
            self.ptr = [0] * len(self.g)
            while True:
                pushed = self.dfs(s, t, inf)
                if pushed == 0:
                    break
                total += pushed

        return total

if __name__ == "__main__":
    dinic = Dinic(6)
    for u, v, c in [
        (0, 1, 10), (0, 2, 10), (1, 2, 2),
        (1, 3, 4), (1, 4, 8), (2, 4, 9),
        (4, 3, 6), (3, 5, 10), (4, 5, 10),
    ]:
        dinic.add_edge(u, v, c)

    print(dinic.max_flow(0, 5))

预期输出

text
19

这个结果表示:在给定容量约束下,从节点 0 到节点 5 最多可以同时输送 19 单位流量。若把边容量替换成任务配额、带宽或可分配资源,算法本身不需要改变。

复杂度与使用边界

对一般有向容量网络,Dinic 的常用最坏复杂度上界是 O(V2E)O(V^2E),空间复杂度为 O(V+E)O(V+E)。它的优势主要来自“按层批量处理增广路”,因此在大量常见稀疏图上通常比逐条找增广路更实用。

容量必须是非负值。整数容量最省心;若使用浮点容量,需要自行处理精度阈值,否则“接近 0 的残量”可能让 BFS 或 DFS 反复访问本应视为饱和的边。对于超大或非常稠密的网络,还应根据数据规模比较 Push-Relabel 等算法。

调试时检查这些不变量

先检查层级:源点层数应为 0,DFS 只走到下一层。再检查残量:正向边减少多少,反向边就必须增加多少,任何残量容量都不能为负。最后检查阶段结束条件:当一轮 DFS 已无法再从源点推出流时才重建分层图。

如果最大流明显偏小,最常见的问题不是 BFS 本身,而是反向边索引、残量更新或 ptr 推进时机写错。把这三个不变量逐项打印验证,通常能很快定位实现错误。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

Dinic 怎样加速最大流

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通