【最大流】Ford-Fulkerson算法——算法设计与分析-Toy模板网

这篇具有很好参考价值的文章主要介绍了【最大流】Ford-Fulkerson算法——算法设计与分析。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、问题定义

1.1 流网络

给定有向图 $G =< V, E, C >$ ，其被称为流网络：

容量： $\forall e \in E, c(e) \ge0$

流量： $\forall e \in E, 0 \leq f(e) \leq c(e)$

剩余容量： $\forall e \in E, c(e)-f(e)$

总流量： $|f|={\textstyle \sum_{\text{e out of s}}f(e) =\textstyle \sum_{\text{e in to t}}f(e) }$ （总流量 = 源点流出量 = 汇点流入量）

fordfulkerson算法求最大流,算法设计与分析,算法,网络

1.2 最大流问题

输入：

①有向图 $G =< V, E, C >$ ，其中， $c(e)\in C$ 表示边 $e$ 的容量

②源点 $s$ ，汇点 $t$

输出：

总流量 $∣ f ∣$

约束目标： ${\textstyle \sum_{\text{e out of s}}f(e)}$
约束条件：
$\quad$ ①容量限制： $0\leq f(e)\leq c(e)$ （边上的流量不能超过容量）
$\quad$ ②流量守恒： ${\textstyle \sum_{\text{e in to v}}f(e)} = {\textstyle \sum_{\text{e out of v}}f(e)}$ （每个顶点进入和流出的流量和相等）

二、算法策略

2.1 算法引入

直观想法：

①对 $\forall e \in E$ ，初始化流量为 $f (e) = 0$

②寻找一条源点 $s$ 到汇点 $t$ 的路径 $P$ ，此路径上的每条边 $e$ 均满足 $f (e) < c (e)$

③按路径 $P$ 上最小剩余容量增加路径流量

④迭代寻找路径 $P$ 直至无法增加路径流量

例如，在下述所给流网络 $G$ 中，选择红线路径作为路径 $P$ ，并增加了11的流量：

fordfulkerson算法求最大流,算法设计与分析,算法,网络

如此迭代寻找 $P$ ，便可以得到解。

但是，显然该方法并不可以得到最优解，例如，当该流网络为如下状态时，

fordfulkerson算法求最大流,算法设计与分析,算法,网络

我们发现，按照直观策略，该网络不能再增加流量。但是如果我们稍作调整，

fordfulkerson算法求最大流,算法设计与分析,算法,网络

如此，我们便成功将网络的流量增加了1。

我们不妨观察一下，我们做了什么样的改动：我们将流量进行了重新分配，缩减了某些边 $v_2,v_3)$ 的流量，并将其重新分配到别的边 $v_2,v_4)$ 上，实际上，上述变动可以看作我们沿着下图中红色路径走了1个流量：

fordfulkerson算法求最大流,算法设计与分析,算法,网络

也就相当于，我们引入了一条返向边 $v_3,v_2)$ ，并发现，如果我们寻找路径时允许反向搜索，则可以增大总流量。

一旦引入了反向边，就需要考虑反向边的权重问题，如何定义正向边及反向边的权重以保证流量调整合理呢？做出以下规定：

反向边权重：描述可缩减流量的上限，即原始边上的流量 $f (e)$

正向边权重：描述可扩充流量的上限，即原始边上的剩余容量 $c (e) - f (e)$

如此，由一条原始边可以生成两条正向、反向边，实现反向搜索，以此来帮助我们更好地寻找到使得总流量增加的路径 $P$ 。

2.2 一些概念

接下来介绍几个概念，并按照上述思路，介绍Ford-Fulkerson算法。

2.2.1 残存网络

对于给定流网络 $G =< V, E, C >$ 和流量 $f$ ，可以得到残存网络 $G_f=<V,E_f>$ ，其中 $\forall c_f(e) \in E_f$ ，其残存容量为：
$c_f(e)=\left\{\begin{matrix}c(e)-f(e) & e为正向边\\ f(e)&e为反向边 \end{matrix}\right.$
残存网络中存储的是容量信息（可扩充及可缩减上限），可以帮助我们快速地发现增广路径（包含返向边的路径）。