《网络流初步》由会员分享，可在线阅读，更多相关《网络流初步（90页珍藏版）》请在金锄头文库上搜索。
1、進撃网络流,BY -外向孤独患者-,【那一天，人类终于回想起了曾一度被它们所支配的恐怖和被囚禁于鸟笼中的那份屈辱。】,第一章那年与网络流的偶遇,【人，只有在放弃战斗的时候才算输，只要坚持战斗，就还没输。】,玛利亚之墙被攻破！,犹豫的骚年眺望远方！,好的那么问题来了。,由于城墙被攻破，有居民们要从S城内逃到最为安全的T城中，S到T之间恰巧是一个无环的有向图，其中有n个城市（包括S，T），m条城市与城市之间的单向直通路，每条路上都有限定的最大人流量。埃尔文团长想知道运送多少居民由S到T的速率。,S,T,2,2,2,2,2,2,2,2,大家总说纷纭莫衷一是。,还是爱尔敏聪明，说这样的问题需要用到网络
2、流。(),可是网络流在一千多年后才被发明出来，大家都不知道网络流是什么。,于是爱尔敏决定给大家补一补网络流的知识。（ ）,阿明的课堂,网络：一个连通的赋权有向图D=（V、E、C），其中V是该图的顶点集，E是有向边(即弧)集，C是弧上的容量。此外顶点集中包括一个起点和一个终点。,概念演绎,流：网络上的流就是由起点流向终点的可行流,假设G(V,E) 是一个有限的有向图，它的每条边(u,v)E都有一个非负值实数的容量c(u,v) 。如果(u,v)不属于E，我们假设c(u,v) = 0 。我们区别两个顶点：一个源点s和一个汇点t。,一道网络流是一个对于所有结点u和v都有以下特性的实数函数（f:VVR）
3、,容量限制:f(u,v)c(u,v)一条边的流不能超过它的容量。,斜对称:f(u,v)=-f(v,u)由u到v的净流必须是由v到u的净流的相反。,流守恒:除非u=s或u=t，否则（wV）f(u,w)=0 一结点的净流是零，除了“制造”流的源点和“消耗”流的汇点。,证明就略了。,阿明的课堂,概念演绎,【弧的流量】容量网络G中的每条弧上的实际流量称作弧的流量。,【可行流】 在容量网络中满足下列条件的网络流称为可行流。 1、弧流量限制：流量要大于等于0且小于等于弧的容量。 2、平衡条件：流量只能从源点流出经过容量网络在汇点会聚。 在网络中不会凭空出现和消失。,【伪流】满足限制条件但不满足平衡条件的网
4、络流。也称为容量可行流。,阿明的课堂,概念演绎,【最大流】在容量网络中，满足弧流量限制条件和平衡条件的最大可行流，称为网络最大流，简称最大流。,【饱和弧与非饱和弧】在容量网络中的某一条弧当流量等于容量时，此弧为饱和弧，否则为非饱和弧。,【零流弧和非零流弧】在容量网络中的某一条弧当流量等于零时，此弧为零流弧，否则为非零流弧。,【链】 在容量网络中，顶点序列（U1，U2Un，V）为一条链，要求两个相连的点之间有一条弧。 注意：链和有向图中有向路径不是相同概念，有向路径中有向边的方向是相同的，但链这里不要求这样。,阿明的课堂,【正方向】设P为容量网络中源点到汇点的一条链，由源点到汇点的方向就为正方向
5、。,概念演绎,【前向弧与后向弧】方向与链的正方向相同的弧称为正向弧。反之称为后向弧。,【增广路】 在容量网络中P是从源点到汇点的一条链，如果：P的所有前向弧都为非饱和弧。则称P是一条增广路（增广链或可改进路）。沿着增广路改进可行流的操作称为增广。,【残留容量】 对于给定的容量网络中某条弧的容量为C，流量为F，残留容量就位C-F。 【残留网络】 以残留容量建成的容量网络。也称为剩余网络。,阿明的课堂,概念演绎,根据网络流的特性和增广路的定义我们可以得到这样的性质：,设增广路P，该路径最多额外流量为c(P)=minc(u,v)|,P,这样一来，设增广的定义流fP为 c(P) P fP(u,v)=
6、-c(P) P 0 其他,给定网络G中的一个流为f,则f+fP依然为网络G的一个流。,阿明的课堂,概念演绎,最大流定理（增广路定理） 如果残留网络上找不到增广路径，则当前流为最大流；反之，如果当前流不为最大流，则一定有增广路径。,阿明的课堂,算法竞演,接下来我们讲最大流算法。,最大流算法大致分为两类：增广路算法和预流推进重标号算法,这次对于网络流的最大流算法中重点介绍增广路算法，因为比较常见。在isap中我们也会接触到预留推进重标号算法。,阿明的课堂,实现方法,Ford-Fulkson 方法 （FF）：,Ford-Fulkson的具体步骤 1、初始化网络中所有边的容量，c继承该边的容量，c初始
7、化为0，其中边即为回退边。初始化最大流为0。 2、在残留网络中找一条从源S到汇T的增广路p。如能找到，则转步骤3,；如不能找到，则转步骤5。 3、在增广路p中找到所谓的“瓶颈”边，即路径中容量最小的边，记录下这个值X，并且累加到最大流中，转步骤4。 4、将增广路中所有c减去X，所有c加上X，构成新的残留网络。转步骤2。 5、得到网络的最大流，退出。,我们发现，能否高效 寻找增广路是各种算 法优劣的主要依据,很显然这个方法 没有告诉我们 如何寻找增广路,阿明的课堂,算法竞演,EK（Edmond-Karp）算法（最短路算法）： 用最最最最最最最最朴素的BFS来寻找增广路,阿明的课堂,时间复杂度O(
8、V*E2) 空间复杂度O(V2),阿明的课堂,算法竞演,我们定义e(u)为节点u上的余流，实际上我们并不需要计算各个h(v)，只需将h(s)标为n，其余标为0，算法也能逐步计算出各个点的h。网络流中的节点(除s, t)仅需要满足流入量不小于流出量。其中流入量大于流出量的节点，我们称之为活动节点。预流推进算法就是不断地将活动结点，变为非活动结点，使得预流成为可行流。具体分为两个方法：,在刚刚的维护距离标号的方法中，我们用到了“预流推进重标号算法”（Push Relabel）,压入操作，选出一个活动顶点u。并依次判断残余网络G中每条边(u, v)，若h(u) = h(v) + 1，则顺着这里条边推
9、流，流量变化量df(u,v)=min(eu,cf(u,v)，同时更新相应的e(u)，e(v)； 重标记操作，选出一个活动结点。如果对于残余网络G中每条边(u, v)，都有h(v)大于或等于h(u)，则需要对u进行重新标号，h(u) = minh(v) + 1；,阿明的课堂,算法竞演,在具体实现中，我们可以选择以下方法： 一般预流推进算法，在残余网络中，以先进先出队列维护活跃点，时间复杂度为O(V*V*V)； 最高标号预流推进算法（HLPP Highest Label Preflow Push），在残余网络图中，每次检查最高标号的活跃点，需要用到优先队列，时间复杂度为O(V*V*E0.5)这是传
10、说中最快的算法。 把预流推进算法与增广路算法结合，时间复杂度为O(V*E*E)；,我们主要介绍方法3，方法1,2可以在“可参考网络资源”的5678学习。,阿明的课堂,算法竞演,SAP（Shortest Augmenting Path）算法： 如果能让每次寻找增广路的时间复杂度降低下来，那么就能够提高算法效率了，sap使用距离标号的最短增广路算法就是这样的。,距离标号及其维护： （1）距离标号：就是某个点到汇点的最小的弧的数量 （2）设点i的标号为Di，那 么如果将满足Di=Dj+1的弧称为允许弧，且增广时只走允许弧，那么就可以达到“怎么走都是最短路”的效果。 （3）每个点的初始标号可以在一开始
11、用一 次从汇点沿所有的反向边BFS求出，实践中可以初始设全部点的距离标号为0 （4）当找增广路过程中发现某点出发没有允许弧时，将这个点的距离标号设为由它出发的所有弧的终点的距离标号的最小值加一。,阿明的课堂,sap另外几个疯狂的常数优化：,算法竞演,（1）当前弧优化（用于邻接表）：初始时当前弧是第一条弧，查找可行弧是从当前弧开始查找，找到一条可行弧就把这条弧设为当前弧。改变距离标号时把当前弧设为第一条弧。当前弧的写法之所以正确就在于任何时候我们都能保证在邻接表中当前弧的前面肯定不存在允许弧。,（2）dinic的借鉴：每次找到路径并增广完毕之后不要将路径中所有的顶点退栈，而是只将瓶颈边以及之后的
12、边退栈,（3）GAP（缺口）优化：当网络中距离标号出现断层时，残余网络中无法得到新流。,阿明的课堂,算法竞演,ISAP（Improved SAP ）算法：推荐算法之一,当SAP优化到这个程度上的时候（准确的说ISAP集合了增广路算法和预流推进重标号算法的优势），它已经升级了！,有了刚刚优化的基础，所以直接丢代码了嘎嘎。,阿明的课堂,时间复杂度O(V2*E) 空间复杂度O(E),阿明的课堂,事实上，代码可以更短。,我们把ISAP的实现方式改为DFS，就像等会要介绍的DINIC一样,阿明的课堂,算法竞演,Dinic算法（阻塞流算法Blocking Flow Algorithm）：推荐算法之一,层次
13、图(分层网络):就是把原图中的点按照到到源的距离分“层”，只保留相邻层(或同层)之间的边的图。 在层次图中求得自己的层数Ai就可以按照Ai=Aj-1这样的有用边寻找增广路。,多路增广：用DFS从源点开始前一层至后一层寻找增广路。,实现步骤： 1、初始化流量 2、根据剩余图计算层次图。若汇点不在层次图内，则算法结束 3、在层次图内用一次dfs过程增广 4、转步骤2,阿明的课堂,时间复杂度O(V2*E) 空间复杂度O(V2),阿明的课堂,算法竞演,一般情况下ISAP比DINIC快（偶不确定。），可以参考“可参考网络资源”的9,阿明的课堂,现在我们就可以解决章首的那个问题了。,请思考：,如果在章首的那个问题中，每个城市也有一定的饱和度，那么这样一来问题应该如何解决呢？(o)？,阿明的课堂,1.http:/ 2.http:/ 3.http:/ 4.http:/ 5.http:/ 6.http:/ 7.http:/ 8.http:/ 9.http:/ _)
