首页 > 笔记 > 图的最大流算法

图的最大流算法

最近坑了最大流。。。疯狂的图论

最大流真是神奇的算法。。。震惊了我好几次

1.网络流问题(NetWork Flow Problem):

给定指定的一个有向图,其中有两个特殊的点源S(Sources)和汇T(Sinks),每条边有指定的容量(Capacity),求满足条件的从S到T的最大流(MaxFlow).

The network flow problem considers a graph G with a set of sources S and sinks T and for which each edge has an assigned capacity (weight), and then asks to find the maximum flow that can be routed from S to T while respecting the given edge capacities.

是不是一脸蒙蔽。。。下面给出一个通俗点的解释

好比你家是汇,自来水厂(有需要的同学可以把自来水厂当成银行之类,以下类似)是源

然后自来水厂和你家之间修了很多条水管子接在一起,水管子规格不一,有的容量大,有的容量小

然后问自来水厂开闸放水,你家收到水的最大流量是多少

如果自来水厂停水了,你家那的流量就是0,当然不是最大的流量,就是零流

但是你给自来水厂交了100w美金,自来水厂拼命水管里通水,但是你家的流量也就那么多不变了,这时就达到了最大流

2.三个基本的性质:

 

如果 C代表每条边的容量 F代表每条边的流量

一个显然的实事是F小于等于C 不然水管子就爆了

这就是网络流的第一条性质 容量限制(Capacity Constraints):F<x,y> ≤ C<x,y>

 

再考虑节点任意一个节点 流入量总是等于流出的量 否则就会蓄水(爆炸危险…)或者平白无故多出水(有地下水涌出?)

这是第二条性质 流量守恒(Flow Conservation):Σ F<v,x> = Σ F<x,u>

当然源和汇不用满足流量守恒 我们不用去关心自来水厂的水是河里的 还是江里的

最后一个不是很显然的性质 是斜对称性(Skew Symmetry): F<x,y> = – F<y,x>

这其实是完善的网络流理论不可缺少的 就好比中学物理里用正负数来定义一维的位移一样

百米起点到百米终点的位移是100m的话 那么终点到起点的位移就是-100m

同样的 x向y流了F的流 y就向x流了-F的流

3.容量网络&流量网络&残留网络:

网络就是有源汇的有向图 关于什么就是指边权的含义是什么

容量网络就是关于容量的网络 基本是不改变的(极少数问题需要变动)

流量网络就是关于流量的网络 在求解问题的过程中

通常在不断的改变 但是总是满足上述三个性质

调整到最后就是最大流网络 同时也可以得到最大流值

images

 

残留网络往往概括了容量网络和流量网络 是最为常用的

残留网络=容量网络-流量网络

这个等式是始终成立的 残留值当流量值为负时甚至会大于容量值

流量值为什么会为负?有正必有负,记住斜对称性!

4.割&割集:

无向图的割集(Cut Set):C[A,B]是将图G分为A和B两个点集 A和B之间的边的全集

A set of edges of a graph which, if removed (or “cut”), disconnects the graph (i.e., forms a disconnected graph).

网络的割集:C[S,T]是将网络G分为s和t两部分点集 S属于s且T属于t 从S到T的边的全集

带权图的割(Cut)就是割集中边或者有向边的权和

Given a weighted, undirected graph G=(V,E) and a graphical partition of V into two sets A and B, the cut of G with respect to A and B is defined as cut(A,B)=sum_(i in A,j in B)W(i,j),where W(i,j) denotes the weight for the edge connecting vertices i and j. The weight of the cut is the sum of weights of edges crossing the cut.

通俗的理解一下:

割集好比是一个恐怖分子 把你家和自来水厂之间的水管网络砍断了一些

然后自来水厂无论怎么放水 水都只能从水管断口哗哗流走了 你家就停水了

割的大小应该是恐怖分子应该关心的事 毕竟细管子好割一些

而最小割花的力气最小

下面我们来考虑如何求最大流。

首先,假如所有边上的流量都没有超过容量(不大于容量),那么就把这一组流量,或者说,这个流,称为一个可行流。一个最简单的例子就是,零流,即所有的流量都是0的流。 我们就从这个零流开始考虑,假如有这么一条路,这条路从源点开始一直一段一段的连到了汇点,并且,这条路上的每一段都满足流量<容量,注意,是严格的<,而不是<=。那么,我们一定能找到这条路上的每一段的(容量-流量)的值当中的最小值delta。我们把这条路上每一段的流量都加上这个delta,一定可以保证这个流依然是可行流,这是显然的。

这样我们就得到了一个更大的流,他的流量是之前的流量+delta,而这条路就叫做增广路。

我们不断地从起点开始寻找增广路,每次都对其进行增广,直到源点和汇点不连通,也就是找不到增广路为止。当找不到增广路的时候,当前的流量就是最大流,这个结论非常重要。

寻找增广路的时候我们可以简单的从源点开始做bfs,并不断修改这条路上的delta量,直到找到源点或者找不到增广路。
这里要先补充一点,在程序实现的时候,我们通常只是用一个c数组来记录容量,而不记录流量,当流量+1的时候,我们可以通过容量-1来实现,以方便程序的实现。

但事实上并没有这么简单,上面所说的增广路还不完整,比如说下面这个网络流模型。

images

 

 

我们第一次找到了1-2-3-4这条增广路,这条路上的delta值显然是1。于是我们修改后得到了下面这个流。(图中的数字是容量)

这时候(1,2)和(3,4)边上的流量都等于容量了,我们再也找不到其他的增广路了,当前的流量是1。

但这个答案明显不是最大流,因为我们可以同时走1-2-4和1-3-4,这样可以得到流量为2的流。

那么我们刚刚的算法问题在哪里呢?问题就在于我们没有给程序一个“后悔”的机会,应该有一个不走(2-3-4)而改走(2-4)的机制。那么如何解决这个问题呢?回溯搜索吗?那么我们的效率就上升到指数级了。

而这个算法神奇的利用了一个叫做反向边的概念来解决这个问题。即每条边(I,j)都有一条反向边(j,i),反向边也同样有它的容量。

我们直接来看它是如何解决的:

在第一次找到增广路之后,在把路上每一段的容量减少delta的同时,也把每一段上的反方向的容量增加delta。即在Dec(c[x,y],delta)的同时,inc(c[y,x],delta)

我们来看刚才的例子,在找到1-2-3-4这条增广路之后,把容量修改成如下

images

 

那么,这么做为什么会是对的呢?我来再通俗的解释一下吧。

事实上,当我们第二次的增广路走3-2这条反向边的时候,就相当于把2-3这条正向边已经是用了的流量给“退”了回去,不走2-3这条路,而改走从2点出发的其他的路也就是2-4。(有人问如果这里没有2-4怎么办,这时假如没有2-4这条路的话,最终这条增广路也不会存在,因为他根本不能走到汇点)同时本来在3-4上的流量由1-3-4这条路来“接管”。而最终2-3这条路正向流量1,反向流量1,等于没有流量。

这就是这个算法的精华部分,利用反向边,使程序有了一个后悔和改正的机会。而这个算法和我刚才算法的代码相比只多了一句话而已。

代码实现

 

Ford-Fulkerson方法依赖于三种重要思想,这三个思想就是在上文中提到的:残留网络,增广路径和割。

Ford-Fulkerson方法是一种迭代的方法。开始时,对所有的u,v∈V有f(u,v)=0,即初始状态时流的值为0。在每次迭代中,可通过寻找一条“增广路径”来增加流值。增广路径可以看成是从源点s到汇点t之间的一条路径,沿该路径可以压入更多的流,从而增加流的值。反复进行这一过程,直至增广路径都被找出来,根据最大流最小割定理,当不包含增广路径时,f是G中的一个最大流。在算法导论中给出的Ford-Fulkerson实现代码如下:

第1~3行初始化各条边的流为0,第4~8就是不断在残留网络Gf中寻找增广路径,并沿着增广路径的方向更新流的值,直到找不到增广路径为止。而最后的最大流也就是每次增加的流值cf(p)之和。在实际的实现过程中,我们可以对上述代码做些调整来达到更好的效果。如果我们采用上面的方法,我们就要保存两个数组,一个是每条边的容量数组c,一个就是上面的每条边的流值数组f,在增广路径中判断顶点u到v是否相同时我们必须判断c[u][v]-f[u][v]是否大于0,但是因为在寻找增广路径时是对残留网络进行查找,所以我们可以只保存一个数组c来表示残留网络的每条边的容量就可以了,这样我们在2~3行的初始化时,初始化每条边的残留网络的容量为G的每条边的容量(因为每条边的初始流值为0)。而更新时,改变7~8行的操作,对于在残留网络上的边(u,v)执行c[u][v]-=cf(p),而对其反向的边(v,u)执行c[v][u]+=cf(p)即可。

现在剩下的最关键问题就是如何寻找增广路径。而Ford-Fulkerson方法的运行时间也取决于如何确定第4行中的增广路径。如果选择的方法不好,就有可能每次增加的流非常少,而算法运行时间非常长,甚至无法终止。对增广路径的寻找方法的不同形成了求最大流的不同算法,这也是Ford-Fulkerson被称之为“方法”而不是“算法”的原因。下面将给出Ford-Fulkerson方法的具体实现细节:

Edmonds-Karp算法实际上就是采用广度优先搜索来实现对增广路径的p的计算,代码如下:

完整实现

poj1273 裸的最大流

第二种实现

Dinic 算法

Dinic算法的基本思路:

1、根据残量网络计算层次图。
2、在层次图中使用DFS进行增广直到不存在增广路
3、重复以上步骤直到无法增广

概念

残量网络:包含反向弧的有向图,Dinic要循环的,每次修改过的图都是残量网络,
层次图:分层图,以[从原点到某点的最短距离]分层的图,距离相等的为一层,(比如上图的分层为{1},{2,4},{3})
增广:在现有流量基础上发现新的路径,扩大发现的最大流量(注意:增加量不一定是这条路径的流量,而是新的流量与上次流量之差)
增广路:在现有流量基础上发现的新路径.
剩余流量:当一条边被增广之后(即它是增广路的一部分,或者说增广路通过这条边),这条边还能通过的流量.
反向弧:我们在Dinic算法中,对于一条有向边,我们需要建立另一条反向边(弧),当正向(输入数据)边剩余流量减少I时,反向弧剩余流量增加I

流程:

用BFS建立分层图  注意:分层图是以当前图为基础建立的,所以要重复建立分层图
用DFS的方法寻找一条由源点到汇点的路径,获得这条路径的流量I 根据这条路径修改整个图,将所经之处正向边流量减少I,反向边流量增加I,注意I是非负数
重复步骤2,直到DFS找不到新的路径时,重复步骤1

 

c++模板题

poj1273 裸的最大流

技巧

  1. 对于多源多汇问题,只需要添加一个超源点和一个超汇点,将其转化为单源单汇问题即可,如下图。

Figure 6 - Reduction of a multiple-source/multiple-sink max-flow problem

  1. 对于在顶点处有流量限制的问题,可以对源图进行扩展,既构建一个新的图,新的图的顶点数是源图的两倍,

源图中每个顶点对应新图中的两个顶点,新的顶点之间有一条边相连,边的权值就是源图顶点的权值,如下图。

Figure 7 - Eliminating vertex-capacities

 


1 COMMENT

  1. 小一米2016-09-07 下午5:31

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×