Dinic 算法是一种用于求解网络流问题的算法，尤其在处理有向图中的最大流问题时非常有效。它是由 Bulgarian 科学家 Danil Dinic 提出的，因此得名。
Dinic 算法基本原理
Dinic 算法主要基于以下原理：
- 分层图（Layered Graph）：首先，将原图按照某种方式分层，使得从源点到汇点的每条路径都只包含一个新添加的边。
- 增广路径（Augmenting Path）：在分层后的图中，寻找一条从源点到汇点的增广路径，即路径上的每条边都有剩余容量。
- 更新容量（Relabel-to-Reduce）：如果找不到增广路径，则对每个节点进行“重标记”，重新计算其层号，直到找到增广路径。
Dinic 算法步骤
- 初始化：创建一个分层图，将所有节点的层号设置为无穷大，源点的层号为0，汇点的层号为1。
- 寻找增广路径：使用 BFS 或 DFS 算法寻找从源点到汇点的增广路径。
- 更新容量：沿着增广路径更新每条边的容量，并将反向边的容量减去相同的值。
- 重标记：如果找不到增广路径，则对每个节点进行“重标记”，重新计算其层号。
- 重复步骤 2-4，直到无法找到增广路径。
图片示例
下面是一个使用 Dinic 算法求解最大流的示例图。
扩展阅读
想要了解更多关于 Dinic 算法的知识，可以参考以下链接：