网络流是图论中的一个重要的问题,关于其介绍可以参考OI-Wiki中的内容(下1,建议先行阅读)。本文就网络流中最大流问题介绍几种算法。

最大流

给出一个源点$S$以及汇点$T$,求$S\to T$的最大流量。

剩余容量

对于一条边$<u,v>$,定义其容量为$c(u,v)$,其流量为$f(u,v)$,那么我么可以得到它的 剩余容量为$c_{f}(u,v)=c(u,v)-f(u,v)$,即容量与流量的差(也就是还能承载多少流量)。值得注意的是,由流函数定义中的$f(u,v)=-f(v,u)$,我们可以发现$c_{f} (v,u)=c(v,u)-f(v,u)=c(u,v)+f(u,v)=f(u,v)$(反向边没有容量),这就是 虚边(反向边)的剩余容量。可以发现$c(u,v)=c_f(u,v)+c_f(v,u)$,即对于一条边而言,其容量为实边与虚边流量和。

残差网络

由上述残差容量引入,对于网络中所有节点以及剩余容量大于0的边构成的子图,我们称为 残差网络(包含虚边)。

增广路

很显然,在原图$G$中如果存在一条路径上所有的边剩余容量都大于0,则这条路被称为增广路(还能承载更多流量)。实际上,寻找增广路就是在残差网络中寻找一条从源点$S$到汇点$T$的简单路径。

EK(Edmond-Karp)算法

由我们刚刚引出的一些概念,我们可以想到一种非常直观的求最大流的方法——寻找增广路,找到最小流量并对其增广。

更具体地说,就是BFS遍历整个残差网络,记录路径,当遇到汇点时即对路径边进行增广,增广的值自然就是最小的剩余容量,同时对答案也增加这个值,从源点重复多次此操作,直到找不到增广路。

为什么需要反向边?下面这张图可以很好地解释:

case

反向边实际上是给算法一个“后悔”的机会。例如,如果第一次进行增广的时候选择的是路径$ 1\to2\to5\to6$,路径最大流量为5,无法再进行增广,这与实际最大流9不符。这时候,我们引入反向边$<5,2>$,其残差流量为5,算法就能够再一次进行增广,路径为$ 1\to4\to5\to2\to3\to6$,路径最大流量为4,累计最大流为9,正是我们需要的答案。

算法时间复杂度$O(|V||E|^2)$。

Dinic算法

与EK算法不同的是,在寻找到一条增广路后,它不需要从源点重新开始寻找增广路,而是可以通过DFS实现多次增广。

更具体的说,首先使用BFS对节点将节点分层,对于每一个阶段按DFS搜索顺序增广(只能走深度不断加深的路径),重复以上操作直到不存在增广路。

算法时间复杂度$O(|V|^2|E|)$,特别地,当算法用于二分图最大匹配问题的时候时间复杂度为$O(|E|\sqrt{|V|})$。

ISAP算法

与Dinic算法类似,ISAP算法优化其中BFS的次数,仅需一次BFS标记深度。

在Dinic算法中,每次DFS结束后都需要用BFS重新去维护节点层次信息,而在ISAP中,算法从汇点$T$到源点$S$只进行一次BFS将节点分层,再从$S$到$T$进行DFS,若出现当前节点流出的流量小于流入的流量时,对其进行加深,当$S$的深度大于等于$|V|$时算法终止。

算法时间复杂度$O(|V|^2|E|)$。


参考资料

Last modification:July 24th, 2020 at 10:50 am
博客维护不易,如果你觉得我的文章有用,请随意赞赏