Ford-Fulkerson算法

本文讲解Ford-Fulkerson算法的思路, 算法本身与证明, 最后会给出模板。Ford-Fulkerson算法是增广路算法的一种, 用于求解最大流问题, 不明背景请看网络流这篇文章。

分析

朴素算法

朴素的想法 (的一种) 是这样的: 在图中DFS, 一旦找到一条从s指向t并且可以在这条路径上添加流量 (即: 每条边$e$都满足$f_e<w_e$) , 那么就在这条路径的所有边上同时不断添加流量, 直到无法再添加 (即: 某条边$e$$f_e=w_e$) 。直到无法再找到任何这样的路径, 即得到最大流。如下图。

朴素想法求最大流

上面的图中, 黑色为边的容量, 红色为边的容量。图1为原来的网络, 其中1为源点, 6为汇点。图二为DFS时可能得到的一个图, 可以看到上面的算法在这里就会停止。而图三是该网络的最大流。可以轻松地验证这一点, 因为从1出发的边都已经满流了, 无法再增加新的流量。注意, DFS可能得到最优解, 但不是一定得到最优解。

所以上述的算法是错误的。但是它错在哪里呢?

改进

观察图3, 这个流比图2多的流如图4:

朴素想法与最大流之差

从图4看, 它是把图2中$2\rightarrow4$已有的流量1 “推了回去” 而产生的。这也正是增广路算法的核心所在。但是, 这看起来不可理喻: 原图中没有的边, 为什么凭空造出来一条就正确呢?

解释

仔细观察图2和图3, 就会发现, $4\rightarrow6$的边流量没变, 仍然是1。但是, $2\rightarrow4$的流量没有了, 那最大流中谁为4提供那一个流量呢? 显然是$1\rightarrow3\rightarrow4$的路径。同理, $1\rightarrow2$的流量也没有变, 它从$2\rightarrow5\rightarrow6$的路径流出去了。这就可以想象成, 节点4不知道是谁给他的流量, 也就是在这个过程中4的上游的信息被屏蔽了, 同时2的下游的信息也被屏蔽了。只要有人能为4提供流量, 他就什么都不知道。同样的, 只要有人能从2运走流量, 他也什么都不知道。这样, 在新的流中, 原本只有一份的流量, $1\rightarrow3\rightarrow 4$流走了一份, $1\rightarrow2\rightarrow5$又流走了一份, 所以流量+1。

所以, $\langle u,v\rangle$的反向边$\langle v,u\rangle$的意义就是: 在$\langle u,v\rangle$有流$f$的时候, 如果有一个路径可以从$v$流入 (称其前面的那段路经为上游) 再从$u$流出 (称其后的那段路径为下游) 且流为$f_0\le f$, 那么就可以认为上游为$v$提供原来的一部分流$f_0$, 而从$u$流入的那些$f_0$ “改道” 从下游流出了。

上面的做法, 可以算作对朴素DFS做法的一个修正, 大概可以理解为: 避免了因DFS顺序不确定而导致的错误。

于是对一个流, 可以对图上所有有流$f$的边$\langle u,v\rangle$建立反向边$\langle v,u\rangle$, 其容量为$f$。这样得到的新的图称为残余网络, 残余网络上从$s$$t$的路径叫做增广路。在残余网络上进行dfs沿着增广路来添加流, 这就是Ford-Fulkerson算法。

算法描述

对网络上的每个流$G(V,E)$, 定义与之对应的残余网络$G'(V,E')$: 若$f_e>0(e=\langle u,v\rangle\in E)$, 那么$e\in E'$$rev(e)=\langle v,u\rangle\in E'$, 并且$w_{rev(e)}=f_e,f_{rev(e)}=0$$E'$中的元素只有刚才描述的那些。那么算法可以描述为:

Ford-Fulkerson算法

输入: 网络$G$ (一个图$G(V,E)$, $E$中的边$e$有权重$w_e\in\mathbb{N_+}$) , $max\_flow=0$

输出: 该网络上的最大流的流量$f$

步骤0. [建立反向边]定义$max\_flow\gets0$, 用邻接表G[V]存储网络; 对$E$中的每条边$e=\langle u,v\rangle$, 作其反向边$e'=\langle v,u\rangle$, 并置$w_{e'}\gets0$

步骤1. [寻找增广路]在$G$上DFS, 寻找从$s$$t$的简单路径, 要求该路径上每条边可用权值$(w_e-f_e)$大于0。若找到, 记该路径上的权值最小的边权值为$f$, 否则$f\gets0$

步骤2. [找到了, 更新残余网络]如果$f>0$, 置$max\_flow\gets max\_flow+f$。对路径上的每条边$e$, 置$f_e\gets f_e+f$。记其反向边为$e'$, 置$w_{e'}\gets w_{e'}+f$。返回1。

步骤3. [没有找到]如果$f=0$, 输出$max\_flow$, 算法结束。

最大流不会超过从$s$出发的所有边的边权和。而该算法中每次进入步骤1后, $f$总是正整数 (也有$f=0$的情况, 此时算法结束) , 所以该算法对整数总是有限的。若记最大流流量上界为$F$, 则该算法最多进入步骤1$(F+1)$次, 而每次进入步骤1需要$O(|E|)$的复杂度进行搜索。所以总的时间复杂度是$O(F|E|)$。但这个复杂度上界是很松的, 实际用起来效率比较高, 所以有时即使估计复杂度偏高也可以使用。对$F$较小的情况则可以轻松应对。

证明

在Ford-Fulkerson算法结束后的残余网络上没有$s\rightarrow t$路径, 所以 (残余网络上) 从$s$可达的所有点构成的集合$S$不包含$t$。记$T=V-S$, 那么$T$不空, 并且$T\cap S=\varnothing$

结论1: 从$S$指向$T$ (满足$u\in S,v\in T$) 的边$e=\langle u, v\rangle$都应当满流, 即$w_e=f_e$。否则, 由于从$s$可达$u$, $s$也可以从$s\rightarrow u\rightarrow v$到达$v$, 那么$v\in S$, 矛盾。

结论2: 从$T$指向$S$ (满足$u\in T,v\in S$) 的边$e=\langle u,v\rangle$流量必为0。否则, $s$可由其反向边到达$u$; 即: 流入$S$的流量为0。 (反向边就是在这里用到的)

对于任意一个流, $S-\{s\}$中的点流入的流量都等于流出的流量, 那么流入$S-\{s\}$的流量$f_{in}$等于从$S$流向$T$的所有边的流量和$S_f$, 这个和不超过从$S$流向$T$的所有边的容量和$S_w$, 写在一起就是$f_{in}=S_f\le S_w$。从而从$s$流出的流量$f_s$一定不超过$S_w$, 因为$f_s$应当是$f_{in}$的一部分。即$f_{s}\le S_w$, 这是对任意流的结论。

而对于残余网络 (注意残余网络也是一个流) , 由结论1, $S_f=S_w$。又由结论2, $f_s$即为$f_{in}$的全部, 所以有$f_s=f_{in}=S_w$, 所以$f_s$为所有流中的最大者。

也可以用反证法。若存在比Ford-Fulkerson算法得到的流更大的流, 仍然观察上面的点集$S$, 此时从$s$流出的流量$f_{s'}$应当超过了$f_x=S_w$, 这时$S-\{s\}$中的点不可能满足流入每个顶点的流量等于流出的流量, 所以这样的流不存在。

至此, 就证明了Ford-Fulkerson算法的正确性。

模板

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

#define V 5005 //V为顶点最大个数, 视数据范围而定
#define INF 0x7fffffffffffffff

using namespace std;
typedef long long ll;
struct edge {
    ll to, w, rev;
};
vector<edge> G[V];
int s, t;//源点和汇点, 是全局变量
bool vis[V];

ll max_flow();
ll dfs(ll u, ll f);
void add_edge(ll from, ll to, ll w);

ll dfs(ll u, ll f) {
    if(vis[u]) return 0;
    vis[u] = true;
    if(u == t) return f;
    for(int i = 0; i < G[u].size(); i++) {
        edge &e = G[u][i];//注意是引用, 需要直接修改原图
        if(!vis[e.to] && e.w > 0) {
            ll curf = dfs(e.to, (f > e.w) ? e.w : f);
            //min函数有些编译器不给过
            if(curf > 0) {
                e.w -= curf;
                //直接修改容量而非同时记录f和w, 只是为了方便
                G[e.to][e.rev].w += curf;
                return curf;
            }
        }
    }
    return 0;
}
ll max_flow() {
    ll maxf = 0;
    while(true) {
        memset(vis, 0, sizeof(vis));
        ll f = dfs(s, INF);
        if(f == 0) break;
        maxf += f;
    }
    return maxf;
}
void add_edge(ll from, ll to, ll w) {
    G[from].push_back(edge(to, G[to].size(), w));
    G[to].push_back(edge(from, G[from].size() - 1, 0));
}

如有发现模板的错误请联系我指正, 我将不胜感激。