网络流算法: Dinic算法

图论相关帖子

• 基本概念
• 图的表示: 邻接矩阵和邻接表
• 图的遍历: 深度优先与广度优先
• 拓扑排序
• 图的最短路径:Dijkstra算法和Bellman-Ford算法
• 最小生成树
• 二分图
• 多源最短路径
• 强连通分量
• 欧拉回路和汉密尔顿回路
• 网络流算法: Edmonds-Karp算法
• 网络流算法: Dinic算法

环境要求

本文所用样例在Windows 11以及Ubuntu 24.04上面编译通过.

1. Windows: 使用[Visual Studio],
2. Ubuntu: 使用 Clang 18.1.3. (Ubuntu 24.04 系统安装版本)
3. GCC 无法编译直接本项目代码, 因为本文代码使用了 C++20 Module, 而 GCC 对此支持不完整.

intro

Dinic 算法是一种用于解决最大流问题的高效算法, 它基于 Ford-Fulkerson 方法, 并通过引入层次图(level graph)的概念来加速寻找增广路径的过程. 我们先从层次图的概念开始.

层次图(Level Graph)

层次图是一个特殊的网络, 它通过引入层次值来表示节点之间的距离. 层次值从源点开始, 按照广度优先搜索(BFS)的顺序进行更新, 直到所有节点都被更新.

构建层次图的过程主要是通过从源点开始进行一次广度优先搜索(BFS), 根据节点到源点的距离来为每个节点分配层次值(level). 以下是构建层次图的具体步骤:

构建层次图的步骤

1. 初始化:

   • 设定源点的层次值为 0.
   • 创建一个队列, 并将源点加入队列中.

2. 执行广度优先搜索(BFS):

   • 从队列中取出一个节点 $u$.
   • 对于 $u$ 的所有邻接节点 $v$, 如果边 $(u,v)$ 在残量图中仍有剩余容量(即该边未被完全利用), 并且 $v$ 还未被访问过(或其层次值尚未确定), 则:
     • 设置 $v$ 的层次值为 $u$ 的层次值加 1, 表示 $v$ 比 $u$ “远” 一个单位距离.
     • 将 $v$ 加入队列中, 以便后续处理 $v$ 的邻接节点.
   • 如果到达汇点, 则停止搜索; 否则继续直到队列为空.

3. 结束条件:

   • 当队列为空时, 说明已经遍历了所有可到达的节点, 并且为这些节点分配了层次值. 此时, 如果汇点没有被访问到(即它没有层次值), 意味着无法再找到从源点到汇点的任何路径, 算法可以终止.
   • 如果汇点有层次值, 则层次图构建完成, 可以进行下一步的深度优先搜索(DFS)以寻找增广路径.

层次图构建样例

1. 初始化. 给定一个原始图, 右侧是它的层次图初始状态.

   

2. 从源点(0)开始出发, 第一层接触到1和3. 将边(0, 1),(0, 3)加入到层次图中.

   

3. 接下来从1和3开始, 第二层接触到2和4. 将边(1, 2),(3, 2),(3, 4)加入到层次图中.

   

4. 最后从2和4开始, 第三层接触到5, 将边(2,5), (4,5)加入到层次图中.
   

5. 由于5是汇点, 所以算法结束. 最后的结果如下:

   

层次图的作用

• 限制搜索范围: 层次图只包含那些按照一定顺序(即按层次值从小到大)排列的节点和边, 这使得在寻找增广路径时只需考虑特定的边集, 减少了不必要的搜索.
• 加快增广路径的查找速度: 由于 DFS 仅沿着层次图中的边进行搜索, 这样可以在较短的时间内找到一条或多条增广路径, 从而提高整个算法的效率.

通过以上步骤, Dinic 算法能够有效地构建层次图, 并利用这个结构快速找到增广路径, 最终求解最大流问题. 这种方法不仅提高了算法的性能, 而且使其实现更加直观易懂.

Dinic 算法步骤

Dinic 算法步骤

1. 构建层次图: 从源点开始进行广度优先搜索(BFS), 为每个节点分配一个层次值(level), 这个值表示该节点到源点的距离. 只有当流量可以通过一系列边从一个较低层次的节点流向较高层次的节点时, 这条路径才会被纳入层次图中.

2. 寻找增广路径: 使用深度优先搜索(DFS)在层次图中寻找从源点到汇点的增广路径. 由于层次图的性质, DFS 可以更高效地找到这些路径.

3. 更新残量图: 一旦找到了一条增广路径, 就沿着这条路径调整流量, 同时更新相应的残量图. 这包括增加正向边的流量并减少反向边的容量.

4. 重复步骤: 重复上述步骤, 直到无法再找到从源点到汇点的增广路径为止.

Dinic 算法样例

1. 初始化: 给定一个原始图如图左侧所示, 如果我们省去容量为 0 的边, 那么左侧图可以看做是一个残量图, 右侧是它的层次图初始状态.

   

2. 利用 DFS 寻找一条增广路径, 我们找到的了一条, 如图所示. 它的容量为 8, 接着我们更新残量图, 得到如图右边所示的图. 注意: 此时 1 -> 2 的边容量为 0, 故而省去.

   

3. 我们继续从残量图获取层级图. 如下:

   

4. 继续寻找增广路径, 找到一条, 如图所示, 容量为 3. 它的容量为 3, 接着我们更新残量图, 得到如图右边所示的图. 注意: 此时 3 -> 4 的边容量为 0, 故而省去.

   

5. 我们继续从残量图获取层级图. 如下:

   

6. 继续寻找增广路径, 找到一条, 如图所示, 容量为 1. 接着我们更新残量图, 得到如图右边所示的图. 注意: 此时 3 -> 2 的边容量为 0, 故而省去.

   

7. 我们继续从残量图获取层级图. 如下:

   

8. 继续寻找增广路径, 找不到了, 所以算法结束.

特点和优势:

• 时间复杂度: Dinic 算法的时间复杂度为 $O(V^{2}E)$, 其中 $V$ 是顶点数, $E$ 是边数. 对于稠密图, 其性能优于 Edmonds-Karp 算法.
• 阻塞流: Dinic 算法每次迭代都会尝试在当前层次图中找到一个"阻塞流", 即无法再在这个层次图中找到任何增广路径. 这种策略使得算法效率更高.
• 应用广泛: 除了用于计算最大流之外, Dinic 算法还常用于解决二分图匹配等问题.

C++ 代码实现

class Dinic {public:explicit Dinic(const AdjList& graph): graph_(graph), residual_graph_(graph.V(), true, true) {BuildResidualGraph();}int MaxFlow(int src, int dst) {int max_flow = 0;while (true) {auto level = BuildLevelGraph(src);auto path = FindArgumentPath(level, src, dst);fmt::println("current path: {}", fmt::join(path, ", "));if (path.empty()) {break;}auto it = std::min_element(path.begin(), path.end(),[](const auto& lhs, const auto& rhs) {return std::get<2>(lhs) < std::get<2>(rhs);});int flow = std::get<2>(*it);if (flow <= 0) {break;}max_flow += flow;for (auto& [u, v, w] : path) {residual_graph_.UpdateWeight(u, v, -flow);residual_graph_.UpdateWeight(v, u, flow);}}return max_flow;}void BuildResidualGraph() {for (Vertex u = 0; u < graph_.V(); u++) {for (Vertex v : graph_.Adj(u)) {residual_graph_.AddEdge(u, v, graph_.GetWeight(u, v));residual_graph_.AddEdge(v, u, 0);}}}AdjList BuildLevelGraph(unsigned src) {AdjList g(graph_.V(), true, true);std::queue<unsigned> q;q.push(src);while (!q.empty()) {auto u = q.front();q.pop();for (auto v : residual_graph_.Adj(u)) {int w = residual_graph_.GetWeight(u, v);if (w <= 0 || g.HasEdge(u, v)) {continue;}g.AddEdge(u, v, w);q.push(v);}}return g;}std::vector<WeightedEdge> FindArgumentPath(const AdjList& graph, unsigned src,unsigned dst) {std::vector<unsigned> parent(graph.V(), UINT_MAX);std::vector<bool> visited(graph.V(), false);std::queue<unsigned> q;q.push(src);while (!q.empty()) {auto curr = q.front();q.pop();if (curr == dst) break;if (visited[curr]) continue;visited[curr] = true;for (auto w : graph.Adj(curr)) {if (visited[w]) continue;if (graph.GetWeight(curr, w) <= 0) continue;parent[w] = curr;q.push(w);}}std::vector<WeightedEdge> path;if (parent[dst] == UINT_MAX) return path;int curr = dst;while (parent[curr] != src) {auto begin = parent[curr];auto end = curr;auto weight = graph.GetWeight(begin, end);path.emplace_back(begin, end, weight);curr = begin;}path.emplace_back(src, curr, graph.GetWeight(src, curr));std::reverse(path.begin(), path.end());return path;}private:const AdjList& graph_;AdjList residual_graph_;
};

代码源文件链接在此: Dinic.ixx