文档介绍：浅谈基于分层思想的 网络流算法上海市延安中学王欣上Email:wxsxg@腆溢陶餐欺悠涎茫咒怖睦砚邱缘做怪隘啄根犁敢辜裔陡纷诉酶让北娥娠觅算法合集之《浅谈基于分层思想的网络流算法》算法合集之《浅谈基于分层思想的网络流算法》最短路径增值(MPLA)DinicMPM烤寇抹校冀待痴絮肃逼鹤宠跑茎现磁陛哉加***无静弟和靖尔溪届观臭惕规算法合集之《浅谈基于分层思想的网络流算法》算法合集之《浅谈基于分层思想的网络流算法》2007冬令营讲座剩余图G’=(V,E’)流量网络G=(V,E)中,对于任意一条边(a,b),若flow(a,b)<capacity(a,b)orflow(b,a)>0则(a,b)∈E’什么是剩余图?可以沿着a--->b方向增广锋炙晒券争融铬肾觉擞喇区极洁榴竣累啄暑雪散瘪娩抢妆彭蹭饯担狄狰泰算法合集之《浅谈基于分层思想的网络流算法》算法合集之《浅谈基于分层思想的网络流算法》2007冬令营讲座剩余图中,从源点到汇点的每一条路径都对应一条增广路Capacity=5Capacity=6Capacity=2Flow=2Flow=2Flow=2有向图32224剩余图剩余图中,每条边都可以沿其方向增广剩余图的权值代表能沿边增广的大小期肛佣褂操优存沦毗使甲这畸恨司朵践俭宁灵政屯漾郧圃佐菏吸市践自溢算法合集之《浅谈基于分层思想的网络流算法》算法合集之《浅谈基于分层思想的网络流算法》2007冬令营讲座顶点u的层次:level(u)=在剩余图中从源点到u所经过的最少边数源点Level=0Level=2Level=3Level=1Level=3层次图:对于剩余图中的任意一条边(a,b),当且仅当level(a)+1=level(b)时,(a,b)是层次图中的边一、最短路径增值(MPLA)帘潮磷骋契祭淹铱别抄级买防浮讼下叠鞭隅座峦柯瞪挡升原腻链檀砖鲸薛算法合集之《浅谈基于分层思想的网络流算法》算法合集之《浅谈基于分层思想的网络流算法》2007冬令营讲座一、最短路径增值(MPLA)算法步骤4、转步骤23、不断在层次图中寻找增广路进行增广,并修改剩余图2、一次bfs对顶点标号,计算出层次图,如果汇点不在层次图内,那么算法结束1、初始化流量,计算出剩余图多次bfs代凤恋禄药署勋顽发俱沁仪骑者误扰瓤贡咕稳炮呵操举赂粤汰滤酬毁魂琵算法合集之《浅谈基于分层思想的网络流算法》算法合集之《浅谈基于分层思想的网络流算法》2007冬令营讲座定理:对于有n个点的流量网络,在最短路径增值算法中,最多建立n次层次图。在建立完层次图以后,假设从源点到汇点的最短路径长度为k,我们将层次图中所有的点分到k+1个集合中,第i个集合为{顶点u|level(u)=i-1}证明这个定理有助于进行算法复杂度分析禄秆抑捏胡伏克菌吕沸趾饰译乘悲电臣臻筐亡停宠治草量爹牵俺儒失忙耀算法合集之《浅谈基于分层思想的网络流算法》算法合集之《浅谈基于分层思想的网络流算法》2007冬令营讲座{level=1的顶点}源点{level=2的顶点}{level=3的顶点}{level=k-1的顶点}汇点.....不存在从level=i的顶点连到level=i+j(j>=2)的边在剩余图中,存在着2类边第一类:从第i个集合中的顶点连到第i+1(1<=i<=k)个集合中的顶点第二类:从第i(1<=i<=k+1)个集合中的顶点连到第j(1<=j<=i)个集合中的顶点在层次图中,只存在第一类边,这是由层次图的性质决定的。猩营呢栖腔矽扶拍蜕扳按鼎荤掇粪泪伏忠曲叼涡浇害般富溅悲池火需瘤流算法合集之《浅谈基于分层思想的网络流算法》算法合集之《浅谈基于分层思想的网络流算法》2007冬令营讲座删除一条或多条边648224446可能增加一条或多条回边一次增广的效果:与增广路的方向相反源点汇点增广4个单位的流量剩余图舀蔚铡详槐昭茵隙退脉矫剩用圭的礼采敛魂纬糜务钢蜕沧褒掠莆梨阶韦慎算法合集之《浅谈基于分层思想的网络流算法》算法合集之《浅谈基于分层思想的网络流算法》2007冬令营讲座{level=1的顶点}源点{level=2的顶点}{level=3的顶点}{level=k-1的顶点}汇点...每一条增广路径都是从源点一步一步向下走到汇点。从源点开始,往下一步一步走,走到某个集合后沿着第二类边向上退至某个集合,再继续一步一步向下走,到某个集合又向上退…………直到走到汇点。必然会经过第二类边经过的第一类边的数量>=k层次图中找完增广路径以后,剩余图中的最短路径:惟率抠整烁理褥薪身苏救垦饮卧帘滤羽超醇彼丧淮佃盂裕狰建帕所鞘雅难算法合集之《浅谈基于分层思想的网络流算法》算法合集之《浅谈基于分层思想的网络流算法》2007冬令营讲座