Dinic 算法求最大流
字数 5249 2025-12-17 14:37:13

Dinic 算法求最大流

问题描述

给定一个有向图 G = (V, E)，其中每条边 e ∈ E 有一个非负的容量 c(e) ≥ 0。图中有两个特殊顶点：一个源点 s（只有出边）和一个汇点 t（只有入边）。最大流问题的目标是找出从源点 s 到汇点 t 的最大流量，即在满足以下两个约束条件的前提下，最大化从 s 流出的总流量：

  1. 容量约束：对于每条边 e，其上的流量 f(e) 不能超过该边的容量 c(e)（即 0 ≤ f(e) ≤ c(e)）。
  2. 流量守恒：对于除 s 和 t 以外的任何顶点 v，流入 v 的总流量必须等于流出 v 的总流量。

Dinic 算法是解决最大流问题的经典算法之一，它通过构造分层图和使用阻塞流来高效地增广流量，时间复杂度为 O(V²E)，但在许多实际图（尤其是单位容量图）中表现优异，比 Edmonds-Karp 算法的 O(VE²) 效率更高。

解题过程（循序渐进讲解）

第一步：核心思想与预备知识

Dinic 算法的核心基于 Ford-Fulkerson 方法，即不断寻找增广路径并增加流量，直到无法增广为止。但它通过两个关键优化显著提升了效率：

  1. 分层图（Level Graph）：在每一轮中，使用 BFS 从源点 s 出发，根据边的剩余容量（即容量减去已用流量）大于0的边进行广度优先搜索，为每个顶点标记一个“层次”（即距离 s 的边数）。由所有从低层次指向高一层次且剩余容量大于0的边构成的子图，称为分层图。
    • 目的：确保每次寻找的增广路径都是最短路径之一（在剩余容量网络中），避免了像早期 DFS 实现那样可能陷入低效的长路径。
  2. 阻塞流（Blocking Flow）：在分层图上，一个阻塞流是指一个流，使得在分层图中，从 s 到 t 的每一条路径都至少有一条边被该流“填满”（即剩余容量变为0）。换句话说，在当前的层次结构下，无法再推送任何流量到汇点 t。
    • 目的：在一次 BFS 构建的分层图上，通过一次（或多步）DFS 找到尽可能多的增广路径，一次性推送一个阻塞流，而不是一条一条地找。

算法流程可以概括为：在每一轮中，先用 BFS 构建分层图，如果汇点 t 无法被到达（即没有层次），则算法终止。否则，在分层图上使用 DFS 寻找阻塞流，并更新整个网络的流量。重复此过程。

第二步：算法伪代码与详细步骤

我们用 G=(V,E) 表示原图，capacity[u][v] 表示边 (u, v) 的容量，flow[u][v] 表示当前边 (u, v) 上的流量。算法通常维护残量网络，残量容量 res[u][v] = capacity[u][v] - flow[u][v]。

数据结构：

  • level[V]：存储每个顶点的层次（BFS 距离）。
  • adj[V]：邻接表，存储图结构。

主函数 Dinic(G, s, t)：

  1. 初始化总流量 max_flow = 0，所有边的流量 flow[u][v] = 0。
  2. 循环执行以下步骤直到跳出：
    a. BFS 构建分层图：
    • 初始化所有 level[u] = -1（表示未访问）。
    • 创建队列，将源点 s 入队，并设置 level[s] = 0。
    • 当队列非空时：
      • 弹出队首顶点 u。
      • 遍历 u 的所有邻接边 (u, v)。如果 level[v] == -1 且残量容量 res[u][v] > 0（即这条边在残量网络中可用），则将 level[v] 设为 level[u] + 1，并将 v 入队。
    • BFS 结束后，如果 level[t] == -1（汇点未被标记层次），说明残量网络中 s 到 t 不连通，算法终止。否则，继续。
      b. 在分层图上 DFS 寻找阻塞流：
    • 调用 DFS(s, t, INF)（INF 表示一个很大的数，如要推送的流量上限）。这个 DFS 过程会尝试从 s 向 t 推送尽可能多的流量，并返回实际推送的流量。
    • 如果 DFS 返回的流量为 0，说明当前分层图上已找不到增广路径（阻塞流已找到），跳回步骤 2a 进行下一轮 BFS 构建新的分层图。
    • 否则，将返回的流量加到 max_flow 上，并重复步骤 2b（即继续在当前同一个分层图上寻找新的增广路径，直到 DFS 返回 0）。
  3. 返回 max_flow。

DFS(u, t, current_flow)：
这个函数尝试从当前顶点 u 向汇点 t 推送最多 current_flow 的流量，并返回实际推送的量。

  1. 如果 u == t，表示到达汇点，返回 current_flow。
  2. 初始化 pushed_flow = 0（本轮从此顶点成功推送出去的流量）。
  3. 遍历 u 的邻接顶点 v（通常使用邻接表迭代器或指针，以避免重复扫描无效边）：
    • 如果 level[v] == level[u] + 1（关键！确保我们只在分层图中前进）且 res[u][v] > 0：
      • possible_flow = min(current_flow - pushed_flow, res[u][v])。这是我们试图通过边 (u, v) 推送的流量。
      • subflow = DFS(v, t, possible_flow)。递归尝试向下推送。
      • 如果 subflow > 0：
        • 更新流量：flow[u][v] += subflow，flow[v][u] -= subflow（注意反向边，用于回退流量）。
        • 相应地更新残量容量：res[u][v] -= subflow，res[v][u] += subflow。
        • pushed_flow += subflow。
      • 如果 pushed_flow == current_flow，说明当前顶点的流出潜力已用尽，中断遍历（这是一个重要优化，称为“当前弧优化”）。
  4. 返回 pushed_flow。

注意：反向边的存在是实现回退流量的关键，它允许算法撤销之前做出的非最优流量分配，从而找到全局最大流。

第三步：一个简单例子

考虑一个简单的网络：
顶点：s, A, B, t。
边：
(s, A): 容量 3
(s, B): 容量 2
(A, B): 容量 5
(A, t): 容量 2
(B, t): 容量 3

执行过程：

  1. 第一轮 BFS：

    • level[s]=0, s 入队。
    • 从 s 出发：A (res=3>0) -> level[A]=1，入队；B (res=2>0) -> level[B]=1，入队。
    • 从 A 出发：B (res=5>0 且 level[B]==-1？不，B已访问，level[B]已是1，但我们需要 level[v]==level[u]+1，即2，条件不成立，忽略)；t (res=2>0) -> level[t]=2，入队。
    • 从 B 出发：t (res=3>0 且 level[t]==-1？不，t已访问，level[t]已是2，条件 level[t]==level[B]+1 (1+1=2) 成立) -> 但 t 已标记，不再操作。
    • BFS结束。分层图包含边： (s,A), (s,B), (A,t), (B,t)。level[t]=2，继续。

  2. 第一轮 DFS 找阻塞流：

    • 从 s 开始 DFS。假设先走 (s,A)。
    • 在 A，尝试走 (A,t)，推送 min(INF, 2) = 2 到 t，成功。返回 subflow=2。
    • 更新：flow[s,A]=2, flow[A,t]=2。反向边更新。
    • s 处 pushed_flow=2。
    • s 继续尝试，走 (s,B)。
    • 在 B，尝试走 (B,t)，推送 min(INF-2, 3)=3 到 t，成功。返回 subflow=3。
    • 更新：flow[s,B]=3, flow[B,t]=3。但注意 (s,B) 容量为2，res[s][B]=2-3? 这里逻辑上，我们推送的 possible_flow 应是 min(current_flow, res)，即 min(INF, 2)=2。所以实际推送的是2。
    • 修正：在 B 尝试 (B,t) 时，possible_flow = min(current_flow - pushed_flow(此时为2), res[B][t]=3) = min(INF-2, 3)，但 current_flow 在递归时是 possible_flow 从上层传下来的。我们重新严谨走一遍：
      • DFS(s, t, INF)。 possible_flow on (s,A) = min(INF,3)=3, 调用 DFS(A, t, 3)。
      • 在 A, possible_flow on (A,t) = min(3,2)=2，调用 DFS(t, t, 2) 返回2。更新 A->t 流量2。A 返回2。
      • s 处 pushed_flow=2，current_flow - pushed_flow 仍很大。尝试 (s,B)：possible_flow = min(很大, 2)=2，调用 DFS(B, t, 2)。
      • 在 B, possible_flow on (B,t) = min(2,3)=2，调用 DFS(t, t, 2) 返回2。更新 B->t 流量2。B 返回2。
      • s 处 pushed_flow=2+2=4。s 返回4。
    • 本轮总流量增加4。此时流量分布： s->A:2, A->t:2; s->B:2, B->t:2。
    • 在当前分层图上再次调用 DFS(s, t, INF)。从 s 出发：
      • (s,A): res=3-2=1>0，level[A]=1，OK。DFS(A, t, min(INF,1)=1)。在 A，边 (A,t) 的 res=0，边 (A,B) 的 res=5>0 但 level[B]=1，不满足 level[B]==level[A]+1 (1+1=2 vs 1)，所以 A 无路可走，返回0。所以 (s,A) 这条路径推送0。
      • (s,B): res=2-2=0，跳过。
      • s 的 DFS 返回0。阻塞流完成。

  3. 第二轮 BFS：

    • 构建新的分层图。注意反向边 (A,s) 的 res 现在是2（因为 flow[s,A]=2，反向边容量对应增加），(B,s) 的 res=2，(t,A) 的 res=2，(t,B) 的 res=2。
    • 从 s 出发：A (res=1>0) -> level[A]=1；B (res=0) 忽略。
    • 从 A 出发：B (res=5>0 且 level[B]==-1) -> level[B]=2；t (res=0) 忽略。
    • 从 B 出发：t (res=1>0 且 level[t]==-1) -> level[t]=3。
    • level[t]=3，继续。

  4. 第二轮 DFS：

    • 从 s 只能到 A (流1)。在 A 到 B (流 min(1,5)=1)。在 B 到 t (流 min(1,1)=1)。成功推送流量1。
    • 更新：flow[s,A]=3, flow[A,B]=1, flow[B,t]=3。总流量变为5。
    • 再次 DFS，s->A 的 res 变为0，无路可走，返回0。

  5. 第三轮 BFS：

    • 从 s 出发，无法到达 t（因为 s->A 和 s->B 的残量均为0）。算法终止。

最终最大流为5。

第四步：时间复杂度与优化

  • 时间复杂度：O(V²E)。原因是：最多有 O(V) 轮 BFS（因为每轮 BFS 后，汇点的层次严格递增，最多到 V-1）。每轮 BFS 是 O(E)。在每轮中，DFS 寻找阻塞流的总复杂度是 O(VE)，因为每条边在构建阻塞流的过程中最多被考虑一次（由于当前弧优化，每条边在每一轮 BFS 中最多被“阻塞”一次，即其残量变为0后就不再被该轮 DFS 访问）。
  • 当前弧优化：在 DFS 过程中，对每个顶点维护一个迭代器（或指针），指向接下来要尝试的边。当一条边的潜力用尽（残量变为0）或发现其无法到达 t 时，就移动迭代器。这确保了每条边在每轮 BFS 对应的阻塞流计算中只被检查一次，是达到 O(VE) 每轮的关键。
  • 多路增广：在分层图上一次 DFS 可以找到多条增广路径（通过递归返回和继续尝试其他边），这比 Edmonds-Karp 算法每次只找一条最短路径更高效。

Dinic 算法因其清晰的层次结构和高效的多路增广，在实践中非常流行，尤其适用于二分图匹配等特定结构的问题（此时复杂度可降至 O(√V E)）。

Dinic 算法求最大流 问题描述 给定一个 有向图 G = (V, E)，其中每条边 e ∈ E 有一个非负的容量 c(e) ≥ 0。图中有两个特殊顶点：一个 源点 s（只有出边）和一个 汇点 t（只有入边）。 最大流问题 的目标是找出从源点 s 到汇点 t 的最大流量，即在满足以下两个约束条件的前提下，最大化从 s 流出的总流量： 容量约束 ：对于每条边 e，其上的流量 f(e) 不能超过该边的容量 c(e)（即 0 ≤ f(e) ≤ c(e)）。 流量守恒 ：对于除 s 和 t 以外的任何顶点 v，流入 v 的总流量必须等于流出 v 的总流量。 Dinic 算法是解决最大流问题的经典算法之一，它通过构造 分层图 和使用 阻塞流 来高效地增广流量，时间复杂度为 O(V²E)，但在许多实际图（尤其是单位容量图）中表现优异，比 Edmonds-Karp 算法的 O(VE²) 效率更高。 解题过程（循序渐进讲解） 第一步：核心思想与预备知识 Dinic 算法的核心基于 Ford-Fulkerson 方法，即不断寻找 增广路径 并增加流量，直到无法增广为止。但它通过两个关键优化显著提升了效率： 分层图（Level Graph） ：在每一轮中，使用 BFS 从源点 s 出发，根据边 的剩余容量（即容量减去已用流量）大于0 的边进行广度优先搜索，为每个顶点标记一个“层次”（即距离 s 的边数）。由所有从低层次指向高一层次且剩余容量大于0的边构成的子图，称为分层图。 目的 ：确保每次寻找的增广路径都是最短路径之一（在剩余容量网络中），避免了像早期 DFS 实现那样可能陷入低效的长路径。 阻塞流（Blocking Flow） ：在分层图上，一个阻塞流是指一个流，使得在分层图中，从 s 到 t 的每一条路径都至少有一条边被该流“填满”（即剩余容量变为0）。换句话说，在当前的层次结构下，无法再推送任何流量到汇点 t。 目的 ：在一次 BFS 构建的分层图上，通过一次（或多步）DFS 找到尽可能多的增广路径，一次性推送一个阻塞流，而不是一条一条地找。 算法流程 可以概括为：在每一轮中，先用 BFS 构建分层图，如果汇点 t 无法被到达（即没有层次），则算法终止。否则，在分层图上使用 DFS 寻找阻塞流，并更新整个网络的流量。重复此过程。 第二步：算法伪代码与详细步骤 我们用 G=(V,E) 表示原图， capacity[u][v] 表示边 (u, v) 的容量， flow[u][v] 表示当前边 (u, v) 上的流量。算法通常维护 残量网络 ，残量容量 res[u][v] = capacity[u][v] - flow[u][v] 。 数据结构 ： level[V] ：存储每个顶点的层次（BFS 距离）。 adj[V] ：邻接表，存储图结构。 主函数 Dinic(G, s, t) ： 初始化总流量 max_flow = 0 ，所有边的流量 flow[u][v] = 0 。 循环执行以下步骤直到跳出： a. BFS 构建分层图 ： 初始化所有 level[u] = -1 （表示未访问）。 创建队列，将源点 s 入队，并设置 level[s] = 0 。 当队列非空时： 弹出队首顶点 u。 遍历 u 的所有邻接边 (u, v)。如果 level[v] == -1 且 残量容量 res[u][v] > 0 （即这条边在残量网络中可用），则将 level[v] 设为 level[u] + 1 ，并将 v 入队。 BFS 结束后，如果 level[t] == -1 （汇点未被标记层次），说明残量网络中 s 到 t 不连通， 算法终止 。否则，继续。 b. 在分层图上 DFS 寻找阻塞流 ： 调用 DFS(s, t, INF)（INF 表示一个很大的数，如要推送的流量上限）。这个 DFS 过程会尝试从 s 向 t 推送尽可能多的流量，并返回实际推送的流量。 如果 DFS 返回的流量为 0，说明当前分层图上已找不到增广路径（阻塞流已找到）， 跳回步骤 2a 进行下一轮 BFS 构建新的分层图。 否则，将返回的流量加到 max_flow 上，并 重复步骤 2b （即继续在当前同一个分层图上寻找新的增广路径，直到 DFS 返回 0）。 返回 max_flow 。 DFS(u, t, current_ flow) ： 这个函数尝试从当前顶点 u 向汇点 t 推送最多 current_flow 的流量，并返回实际推送的量。 如果 u == t ，表示到达汇点，返回 current_flow 。 初始化 pushed_flow = 0 （本轮从此顶点成功推送出去的流量）。 遍历 u 的邻接顶点 v（通常使用邻接表迭代器或指针，以避免重复扫描无效边）： 如果 level[v] == level[u] + 1 （ 关键！确保我们只在分层图中前进 ）且 res[u][v] > 0 ： possible_flow = min(current_flow - pushed_flow, res[u][v]) 。这是我们试图通过边 (u, v) 推送的流量。 subflow = DFS(v, t, possible_flow) 。递归尝试向下推送。 如果 subflow > 0 ： 更新流量： flow[u][v] += subflow ， flow[v][u] -= subflow （注意反向边，用于回退流量）。 相应地更新残量容量： res[u][v] -= subflow ， res[v][u] += subflow 。 pushed_flow += subflow 。 如果 pushed_flow == current_flow ，说明当前顶点的流出潜力已用尽， 中断遍历 （这是一个重要优化，称为“当前弧优化”）。 返回 pushed_flow 。 注意 ：反向边的存在是实现回退流量的关键，它允许算法撤销之前做出的非最优流量分配，从而找到全局最大流。 第三步：一个简单例子 考虑一个简单的网络： 顶点：s, A, B, t。 边： (s, A): 容量 3 (s, B): 容量 2 (A, B): 容量 5 (A, t): 容量 2 (B, t): 容量 3 执行过程 ： 第一轮 BFS ： level[ s ]=0, s 入队。 从 s 出发：A (res=3>0) -> level[ A]=1，入队；B (res=2>0) -> level[ B ]=1，入队。 从 A 出发：B (res=5>0 且 level[ B]==-1？不，B已访问，level[ B]已是1，但我们需要 level[v]==level[u]+1 ，即2，条件不成立，忽略)；t (res=2>0) -> level[ t ]=2，入队。 从 B 出发：t (res=3>0 且 level[ t]==-1？不，t已访问，level[ t]已是2，条件 level[t]==level[B]+1 (1+1=2) 成立) -> 但 t 已标记，不再操作。 BFS结束。分层图包含边： (s,A), (s,B), (A,t), (B,t)。level[ t ]=2，继续。 第一轮 DFS 找阻塞流 ： 从 s 开始 DFS。假设先走 (s,A)。 在 A，尝试走 (A,t)，推送 min(INF, 2) = 2 到 t，成功。返回 subflow=2。 更新：flow[ s,A]=2, flow[ A,t ]=2。反向边更新。 s 处 pushed_ flow=2。 s 继续尝试，走 (s,B)。 在 B，尝试走 (B,t)，推送 min(INF-2, 3)=3 到 t，成功。返回 subflow=3。 更新：flow[ s,B]=3, flow[ B,t]=3。但注意 (s,B) 容量为2， res[s][B]=2-3? 这里逻辑上，我们推送的 possible_flow 应是 min(current_flow, res) ，即 min(INF, 2)=2 。所以实际推送的是2。 修正：在 B 尝试 (B,t) 时， possible_flow = min(current_flow - pushed_flow(此时为2), res[B][t]=3) = min(INF-2, 3) ，但 current_flow 在递归时是 possible_flow 从上层传下来的。我们重新严谨走一遍： DFS(s, t, INF)。 possible_flow on (s,A) = min(INF,3)=3, 调用 DFS(A, t, 3)。 在 A, possible_flow on (A,t) = min(3,2)=2，调用 DFS(t, t, 2) 返回2。更新 A->t 流量2。A 返回2。 s 处 pushed_flow =2， current_flow - pushed_flow 仍很大。尝试 (s,B)： possible_flow = min(很大, 2)=2，调用 DFS(B, t, 2)。 在 B, possible_flow on (B,t) = min(2,3)=2，调用 DFS(t, t, 2) 返回2。更新 B->t 流量2。B 返回2。 s 处 pushed_flow =2+2=4。s 返回4。 本轮总流量增加4。此时流量分布： s->A:2, A->t:2; s->B:2, B->t:2。 在当前分层图上再次调用 DFS(s, t, INF)。从 s 出发： (s,A): res=3-2=1>0，level[ A]=1，OK。DFS(A, t, min(INF,1)=1)。在 A，边 (A,t) 的 res=0，边 (A,B) 的 res=5>0 但 level[ B]=1，不满足 level[B]==level[A]+1 (1+1=2 vs 1)，所以 A 无路可走，返回0。所以 (s,A) 这条路径推送0。 (s,B): res=2-2=0，跳过。 s 的 DFS 返回0。阻塞流完成。 第二轮 BFS ： 构建新的分层图。注意反向边 (A,s) 的 res 现在是2（因为 flow[ s,A ]=2，反向边容量对应增加），(B,s) 的 res=2，(t,A) 的 res=2，(t,B) 的 res=2。 从 s 出发：A (res=1>0) -> level[ A ]=1；B (res=0) 忽略。 从 A 出发：B (res=5>0 且 level[ B]==-1) -> level[ B ]=2；t (res=0) 忽略。 从 B 出发：t (res=1>0 且 level[ t]==-1) -> level[ t ]=3。 level[ t ]=3，继续。 第二轮 DFS ： 从 s 只能到 A (流1)。在 A 到 B (流 min(1,5)=1)。在 B 到 t (流 min(1,1)=1)。成功推送流量1。 更新：flow[ s,A]=3, flow[ A,B]=1, flow[ B,t ]=3。总流量变为5。 再次 DFS，s->A 的 res 变为0，无路可走，返回0。 第三轮 BFS ： 从 s 出发，无法到达 t（因为 s->A 和 s->B 的残量均为0）。算法终止。 最终最大流为5。 第四步：时间复杂度与优化 时间复杂度 ：O(V²E)。原因是：最多有 O(V) 轮 BFS（因为每轮 BFS 后，汇点的层次严格递增，最多到 V-1）。每轮 BFS 是 O(E)。在每轮中，DFS 寻找阻塞流的总复杂度是 O(VE)，因为每条边在构建阻塞流的过程中最多被考虑一次（由于当前弧优化，每条边在每一轮 BFS 中最多被“阻塞”一次，即其残量变为0后就不再被该轮 DFS 访问）。 当前弧优化 ：在 DFS 过程中，对每个顶点维护一个迭代器（或指针），指向接下来要尝试的边。当一条边的潜力用尽（残量变为0）或发现其无法到达 t 时，就移动迭代器。这确保了每条边在每轮 BFS 对应的阻塞流计算中只被检查一次，是达到 O(VE) 每轮的关键。 多路增广 ：在分层图上一次 DFS 可以找到多条增广路径（通过递归返回和继续尝试其他边），这比 Edmonds-Karp 算法每次只找一条最短路径更高效。 Dinic 算法因其清晰的层次结构和高效的多路增广，在实践中非常流行，尤其适用于二分图匹配等特定结构的问题（此时复杂度可降至 O(√V E)）。