【运筹优化】网络最大流问题及三种求解算法详解 + Python代码实现

---

标题中时间复杂度用到的符号说明：f 代表最大流的大小，m代表边的数量，n 代表节点的数量
本博客学习自：B站-ShusenWang

最大流问题，是网络流理论研究的一个基本问题，求网络中一个可行流 $f?$，使其流量 $v(f)$达到最大， 这种流 $f$ 称为最大流，这个问题称为 (网络)最大流问题。

最大流问题是一个特殊的线性规划问题，就是在容量网络中，寻找流量最大的可行流。

下面我们用一个例子来直观理解网络最大流问题

如下图所示，S处是一个水源，图中的弧是水管，管道由于材质、直径的不同，其所能承受的输水量也不同，所以就出现了下图所示的不同数值的弧，我们的目标是将水源从 S 通过管道运输到 T 点，且在满足管道能承受的输水量的前提下尽可能使得输送到 T 点的水最大化。

这就是最大流问题。

---

残存网络其实就是用边的剩余容量来表示每条边，如下图所示的残存网络。S->v2这条边上的数字“2”代表这条边剩余可通过容量为2。

实际写代码只用残存网络即可求出最大流

一条能从起点S到达起点T的流量大于0的路径就被称为增广路径，通过增广路径，流量一定会增加。

该算法概况起来，就是在残存网络中不断寻找增广路径，每找到一条增广路径，就递增最大流 $f$，并更新残存网络，直到残存网络中不存在增广路径，则此时f即为最终的最大流。

Ford-Fulkerson 算法是通过 DFS（深度优先遍历）的方式在当前残存网络中寻找增广路径的。

根据木桶原理，增广路径的流量等于该路径的边的最小剩余流量。如下图所示的增广路径，它的流量就是3，因为 v4->t 的容量为3

在找到增广路径后，我们要更新残存网络。首先就是对该增广路径的正向边进行更新，将正向边的剩余流量全部减去3

然后对该增广路径的反向边进行更新（反向边在初始化的时候，剩余流量都为0，所以在上面的图中没有画出来，反向边的作用就是让算法可以反悔，从而通过多次迭代，找到最优解），反向边的剩余流量全部加上3

添加反向边是这一算法能够精确求解最大流问题的基础保障

然后重复上述过程，直到找不到增广路径，算法结束

Ford-Fulkerson 算法的整体实现思路如下，其实就是不断从残存网络寻找增广路径的过程

完整代码

测试案例

程序输出

---

Edmons-Karp 算法比 Ford-Fulkerson 算法晚16年提出，它和 Ford-Fulkerson 算法唯一的区别在于寻找增广路径的方式不同，其余步骤完全一样。Edmons-Karp 算法在寻找增广路的时候是将残存网络看作一个无权图然后求S到T的最短路，这条最短路上的最小剩余流量如果大于0，那么就作为增广路径，进行残存网络的更新。

Edmons-Karp 算法贡献在于，它具有比 Ford-Fulkerson 算法更小的时间复杂度，Ford-Fulkerson 算法的时间复杂度受最大流大小影响，而 Edmons-Karp 算法只受节点数量和边的数量的影响

本代码使用 BFS（广度优先搜索） 求最短路，测试案例还是和上面的一样

程序输出

---

由于边的数量 m 通常远远大于节点数量 n，所以通常情况下 Dinic 算法比 Edmons-Karp 算法更快。而且 Dinic 算法发表时间比 Edmons-Karp 算法还要早两年。

为了更好的讲解 Dinic 算法，下面先介绍一个重要的概念 Level Graph

Level Graph 是原图的一个子图，保留了原图中的所有节点和一部分边，下面图解 Level Graph 的构造过程

首先，将 S 作为 Level Graph 的第零层

然后，从 S 出发，可以到达的点有 v2，将 v2 加入 Level Graph，记作第一层 ，保留第零层到第一层的边

看一下右边的原图，从第一层可以到达的节点有 S 和 v4，由于 S 已经在 Level Graph 中了，所以不考虑。将 v4 加入 Level Graph，记作第二层，保留第一层到第二层的边。

看一下右边的原图，从第二层可以到达的节点有 v1、v2和v3，由于 v2 已经在 Level Graph中了，所以只考虑 v1和v3，将它们加入 Level Graph，记作第三层，保留第二层到第三层的边

看一下右边的原图，从第三层可以到达所有节点，由于目前只剩下节点 t 没有加入 Level Graph，所以将 t 加入 Level Graph，记作第四层，保留第三层到第四层的边。

至此，原图的 Level Graph 构造完毕！Level Graph 中节点的层数代表着从起点到达该起点所需要的最少步数（其实就是无权图下的最短路），这么看来，Dinic 算法其实结合了 Ford-Filkerson 和 Edmons-Karp 两个算法的思想呀！

介绍完 Level Graph，下面开始正式介绍 Dinic 算法！

程序输出

---

本节测试所用的案例是随机案例，如下图所示，根据指定的 m 和 n，构造一个中间有两层节点的网络图

在测试1中，固定 m = 10，n 从 2 开始以 1 的步长一直自增到 20

在测试2中，固定 n = 10，m 从 2 开始以 1 的步长一直自增到 20

• 当点的数量远大于边的数量时，采用 Edmons-Karp 算法
• 否则采用 Ford-Filkerson 算法和 Dinic 算法（在我的测试中，这两种该算法性能差不多，不过 Dinic 算法看起来更加稳健一些，当然有条件的话最好都尝试一下）