欢迎来到天天文库
浏览记录
ID:52849776
大小:192.59 KB
页数:35页
时间:2020-03-26
《浅谈基于,分层思想,网络,流算法.pptx》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、浅谈基于分层思想的网络流算法2007冬令营讲座最短路径增值(MPLA)DinicMPM2007冬令营讲座剩余图G’=(V,E’)流量网络G=(V,E)中,对于任意一条边(a,b),若flow(a,b)0则(a,b)∈E’什么是剩余图?可以沿着a--->b方向增广2007冬令营讲座剩余图中,从源点到汇点的每一条路径都对应一条增广路Capacity=5Capacity=6Capacity=2Flow=2Flow=2Flow=2有向图32224剩余图剩余图中,每条边都可以沿其方向增广剩余图的
2、权值代表能沿边增广的大小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、初始化流量,计算出剩
3、余图多次bfs2007冬令营讲座定理:对于有n个点的流量网络,在最短路径增值算法中,最多建立n次层次图。在建立完层次图以后,假设从源点到汇点的最短路径长度为k,我们将层次图中所有的点分到k+1个集合中,第i个集合为{顶点u
4、level(u)=i-1}证明这个定理有助于进行算法复杂度分析2007冬令营讲座{level=1的顶点}源点{level=2的顶点}{level=3的顶点}{level=k-1的顶点}汇点.....不存在从level=i的顶点连到level=i+j(j>=2)的边在剩余图中,存在着2类边第一类:从第i个集合中的顶点连到
5、第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的顶点}汇点...每一条增广路径都是从源点一步一步向下走到汇点。从源点开始,往下一步一步走,走到某个集合后
6、沿着第二类边向上退至某个集合,再继续一步一步向下走,到某个集合又向上退…………直到走到汇点。必然会经过第二类边经过的第一类边的数量>=k层次图中找完增广路径以后,剩余图中的最短路径:2007冬令营讲座层次图中增广路径长度序列严格递增最多建n次层次图一、最短路径增值(MPLA)1<=路径长度<=n-12007冬令营讲座一、最短路径增值(MPLA)建层次图:复杂度分析最多有n层O(n*m)每层做一次bfs标号O(m)2007冬令营讲座一、最短路径增值(MPLA)复杂度分析找增广路:最多有n层最多找m次增广路找增广路bfsO(m)O(n*m*m
7、)每增广一次至少删除一条边2007冬令营讲座一、最短路径增值(MPLA)对于中小规模数据速度快复杂度O(n*m2)程序简短2007冬令营讲座二、Dinic4、转步骤2算法步骤1、初始化流量,计算出剩余图3、一次dfs过程找增广2、一次bfs对顶点标号,计算出层次图,如果汇点不在层次图内,那么算法结束2007冬令营讲座二、Dinicabdcef10551055源汇栈abcde5500后退到原路径中从源点能够到达的最远点f2007冬令营讲座ps;While源点没有被删除up.top;ifu<>tifoutdegree(u)>0设(u,v)
8、为层次图中的一条边;pp,v;else从p和层次图中删除点u,以及和u连接的所有边;else增广p(删除了p中的饱和边);令p.top为p中从s可到达的最后顶点;endwhile2007冬令营讲座二、Dinic建层次图:+dfs找增广路:O(n*m)O(n*n*m)复杂度分析2007冬令营讲座层次图中最多找m次增广路每次在dfs中最多前进n次,花费O(n)每次修改流量花费O(n)一次Dfs复杂度为O(m*n)2007冬令营讲座二、Dinic复杂度O(n2*m)程序简短对于较大规模的数据实际速度很快2007冬令营讲座三、Dinic的应用N
9、oi2006最大获利:一共有N个通讯信号中转站,建立第i个通讯中转站需要的成本为Pi(1≤i≤N)。另有M个用户群,第i个用户会使用中转站Ai和中转站Bi进行通讯,公司可以获益Ci。(1≤i≤
此文档下载收益归作者所有