最大流与最小割算法详解：Dinic 算法实现与优化

最大流与最小割算法：Dinic 算法详解

Dinic 算法是目前工程中最常用的高效最大流算法，由以色列数学家 Yefim Dinitz 于 1970 年提出。它在 Edmonds-Karp 算法的基础上做了两大核心优化：

1. 分层图构建：用 BFS 为残量网络的顶点按到源点的最短距离（边数）分层，保证只在层间单向流动（仅允许从第 k 层流向第 k+1 层）；
2. 阻塞流查找：用 DFS 在分层图中查找阻塞流（分层图中不存在增广路径时的流），一次 DFS 可批量找到多条增广路径，大幅减少迭代次数。

Dinic 算法的时间复杂度为 O(V²E)（V 为顶点数，E 为边数），在实际应用中（尤其是二分图等特殊图）效率远超 Edmonds-Karp。

一、核心概念

概念	定义
分层图	对残量网络做 BFS，给每个顶点标记层次（到源点的最短边数），仅保留 u 到 v 且 level[v]=level[u]+1 的边，形成的有向无环图。
阻塞流	分层图中无法再找到增广路径时的流，即分层图的'饱和流'，一次阻塞流可包含多条增广路径。
当前弧优化	DFS 查找阻塞流时，记录每个顶点的当前遍历到的边索引，避免重复遍历无效边，进一步提升效率。

二、算法核心原理

1. 分层图是基础：分层保证了增广路径的最短性，且分层图是有向无环图，无环的特性让 DFS 查找阻塞流时不会陷入循环；
2. 阻塞流批量增广：一次 DFS 可在分层图中找到多条增广路径，将这些路径的流量一次性更新，比 Edmonds-Karp 的'一条路径一次更新'效率更高；
3. 迭代终止条件：当 BFS 无法给汇点分层（即残量网络中不存在源点到汇点的路径）时，当前流即为最大流。

三、算法步骤

Dinic 算法的执行流程分为 分层 → 找阻塞流 → 更新残量网络 三步循环，直到无法分层为止：

1. 步骤 1：BFS 构建分层图
   • 初始化顶点层次 level[] 为 -1（未访问），源点层次 level[s] = 0；
   • 用 BFS 遍历残量网络，仅访问残量容量 >0 的边，给每个可达顶点标记层次（level[v]=level[u]+1）；
   • 若汇点 t 无法被分层（level[t]=-1），算法终止，当前总流量即为最大流。
2. 步骤 2：DFS 查找阻塞流（带当前弧优化）
   • 初始化当前弧索引 ptr[] 为 0（记录每个顶点的当前遍历边）；
   • 从源点 s 出发，在分层图中 DFS：仅遍历 level[v]=level[u]+1 且残量 >0 的边；
   • 递归计算从当前顶点 u 到汇点 t 的可增广流量，若 u=t 则返回当前流量，否则取所有邻边的可增广流量的最小值；
   • 更新当前边的残量容量和反向边的残量容量，同时更新当前弧索引（跳过已饱和的边）。
3. 步骤 3：累加阻塞流流量
   • 将找到的阻塞流流量累加到总最大流中；
   • 重复步骤 1-2，直到 BFS 无法分层为止。

四、完整代码实现（Python，带当前弧优化）

from collections import deque

class Dinic:
     ():
        
        .n = n
        .source = source
        .sink = sink
        
        .graph = [[]  _  (n)]
        
        .level = [-] * n
        
        .ptr = [] * n

     ():
        
        
        forward = (v, capacity, (.graph[v]))
        
        backward = (u, , (.graph[u]))
        .graph[u].append(forward)
        .graph[v].append(backward)

     ():
        
        .level = [-] * .n
        q = deque()
        
        .level[.source] = 
        q.append(.source)
         q:
            u = q.popleft()
             (v, cap, _)  .graph[u]:
                
                 .level[v] == -  cap > :
                    .level[v] = .level[u] + 
                    q.append(v)
                    
                     v == .sink:
                         
        
         .level[.sink] != -

     ():
        
         u == .sink:
             flow_limit
        
         .ptr[u] < (.graph[u]):
            edge_idx = .ptr[u]
            v, cap, rev_idx = .graph[u][edge_idx]
            
             .level[v] == .level[u] +   cap > :
                
                min_flow = (flow_limit, cap)
                aug_flow = .dfs_flow(v, min_flow)
                 aug_flow > :
                    
                    .graph[u][edge_idx] = (v, cap - aug_flow, rev_idx)
                    
                    rev_v, rev_cap, rev_rev_idx = .graph[v][rev_idx]
                    .graph[v][rev_idx] = (rev_v, rev_cap + aug_flow, rev_rev_idx)
                     aug_flow
            
            .ptr[u] += 
        
         

     ():
        
        total_flow = 
        
         .bfs_level():
            
            .ptr = [] * .n
            
             :
                flow = .dfs_flow(.source, ())
                 flow == :
                    
                total_flow += flow
         total_flow

     ():
        
        
        visited = [] * .n
        q = deque()
        q.append(.source)
        visited[.source] = 
         q:
            u = q.popleft()
             (v, cap, _)  .graph[u]:
                  visited[v]  cap > :
                    visited[v] = 
                    q.append(v)
        S = [i  i  (.n)  visited[i]]
        T = [i  i  (.n)   visited[i]]
        
        cut_capacity = 
         u  S:
             (v, cap, rev_idx)  .graph[u]:
                 v  T:
                    
                    rev_cap = .graph[v][rev_idx][]
                    cut_capacity += (cap + rev_cap)
         S, T, cut_capacity


 __name__ == :
    
    
    n = 
    source = 
    sink = 
    dinic = Dinic(n, source, sink)
    dinic.add_edge(, , )
    dinic.add_edge(, , )
    dinic.add_edge(, , )
    dinic.add_edge(, , )
    dinic.add_edge(, , )

    
    max_flow_val = dinic.max_flow()
    ()
    

    
    S, T, cut_cap = dinic.min_cut()
    ()
    ()
    ()