网络分析最短路和最大流问题

Page16.3最短路问题问题描述：就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路.有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。Page2最短路问题例渡河游戏一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。Page3最短路问题定义：1）人—M（Man），狼—W（Wolf），羊—G（Goat），草—H（Hay）2）点——vi表示河岸的状态3）边——ek表示由状态vi经一次渡河到状态vj4）权——边ek上的权定为1我们可以得到下面的加权有向图Page4最短路问题状态说明：v1,u1=(M,W,G,H);v2,u2=(M,W,G);v3,u3=(M,W,H);v4,u4=(M,G,H);v5,u5=(M,G)此游戏转化为在下面的二部图中求从v1到u1的最短路问题。v1v2v3v4v5u5u4u3u2u1(M,W,G,H)(M,W,G)(M,G,H)(M,G)(M,W,H)(M,W,H)(M,G,H)(M,W,G,H)(M,W,G)(M,G)Page5最短路问题迪科斯彻(迪杰斯特拉Dijkstra)标号算法的基本思路：若序列{vs,v1…..vn-1,vn}是从vs到vt间的最短路，则序列{vs,v1…..vn-1}必为从vs到vn-1的最短路。假定v1→v2→v3→v4是v1→v4的最短路，则v1→v2→v3一定是v1→v3的最短路，v2→v3→v4也一定是v2→v4的最短路。v1v2v3v4v5Page6最短路问题求网络图的最短路，设图的起点是vs,终点是vt,以vi为起点vj为终点的边记为(i,j)距离为dijLsj—起点vs到点vj的最短路长；k(i,j)=Lsi+dij.Dijkstra算法步骤：从s点出发，因Lss=0,.并将Lss的值标注在s点旁的小方框内。表示s点已标注。从s点出发，找出与s点相邻的所有的点，记为点集V1，取vr，s.t.，，则将r点标注，并将Lsr的值标注在r点旁的小方框内。从已标注的点出发，找出与这些点相邻的所有未标注的点记为点集V2，取vt，s.t.，，则将t点标注，并将Lst的值标注在t点旁的小方框内。重复第三步，一直到t点得到标号为止，它旁边的小方框表的数值就是s点到t点的最小距离。}d+{Lmin=Lsissvsr1iV}d+L;d+{Lmin=Lrisrsissvst2iVPage7最短路问题例3求下图v1到v7的最短路长及最短路线2v7已标号，计算结束。从v1到v7的最短路长是10,最短路线：v1→v3→v6→v5→v72057452761776310Page9最短路问题从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj。Page10最短路问题例3.1求下图v1到各点的最短距离及最短路线。①②③④⑤⑥⑦⑧4526178393261216180452231059612641166188122482418所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。Page11最短距离的矩阵算法1112221111121ninnnininiiinininivvvddddddddddddvvvvB网络图的矩阵表示dij表示i点到j点两相邻点间的距离，若i和j点不相邻，则dij=∞Page12最短距离的矩阵算法06360124310672607247027205250例3中用矩阵算法求各点之间的最短距离图的矩阵表示04381010401244631035712823062710456072104727056127250Page13最短距离的矩阵算法点之间直接相邻距离。和表示其中jiddDijij000时，停止直到1kkDD12lg)1lg(2lg)1lg(12112k1kpkpp即，有网络图的矩阵表示0001111;minrjirijijijijddddjiddD其中它们之间的最近距离。时，点之间至多相隔一个点和表示其中。它们之间的最近距离，时，点之间至多相隔三个点和表示其中};min{1112222rjirijijijijddddjiddD。它们之间的最近距离，个点时，点之间至多相隔和表示其中};min{12111kkrjkirkijkijkkijkijddddjiddDPage146.5网络的最大流如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。Page15网络的最大流基本概念：1.容量网络：对网络上的每条弧(vi,vj)都给出一个最大的通过能力，称为该弧的容量，简记为cij。容量网络中通常规定一个发点(也称源点，记为s)和一个收点(也称汇点，记为t)，网络中其他点称为中间点。s①②③④t4844122679Page16网络的最大流2.网络的最大流是指网络中从发点到收点之间允许通过的最大流量。3.流与可行流流是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上的负载量记为fij。若fij=0，称为零流。满足以下条件的一组流称为可行流。容量限制条件。容量网络上所有的弧满足：0≤fij≤cij中间点平衡条件。),(0),(),(tsivvfvvfijji若以v(f)表示网络中从s→t的流量，则有：),(),()(tjjsvvfvvffvPage17网络的最大流可行流{f(vi，vj)}满足：),(0),(),(tsivvfvvfijji),(),(0jijivvcvvfPage180),,(),(0maxijjiijijjttVjtjVjjssVjsjVjijiiVjijVjfjiVvvcffffffftsiVvfffztsi但网络的最大流最大流问题的数学模型:注：（vi，vj）∈E，则有fij≥0Page19网络的最大流结论：任何网络上一定存在可行流。（零流即是可行流）网络最大流问题：指满足容量限制条件和中间点平衡的条件下，使f值达到最大。Page20网络的最大流割与割集割是指容量网络中的发点和收点分割开，并使s→t的流中断的一组弧的集合。割容量是组成割集合中的各条弧的容量之和，用表示。),(VVc),(),(),(),(VVjijivvcVVc如下图中，AA′将网络上的点分割成两个集合。并有，称弧的集合{(v1,v3),(v2,v4)}是一个割，且的流量为18。VV,VtVs,VVPage21网络的最大流●stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(4)7(6)AA’BB’Page22网络的最大流定理1设网络N中一个从s到t的流f的流量为v(f)，(V,V´)为任意一个割集，则v(f)=f(V,V´)f(V´,V)推论1对网络N中任意流量v(f)和割集(V,V´)，有v(f)c(V,V´)[证明]w=f(V,V´)f(V´,V)f(V,V´)c(V,V´)推论2最大流量v＊(f)不大于最小割集的容量，即：v＊(f)min{c(V,V´)}定理2在网络中s→t的最大流量等于它的最小割集的容量，即：v＊(f)=c＊(V,V´)Page23网络的最大流增广链在网络的发点和收点之间能找到一条链，在该链上所有指向为s→t的弧，称为前向弧，记作μ+,存在fc；所有指向为t→s的弧，称为后向弧，记做μ－，若f0，则称这样的链为增广链。f1c1sf20f30f4c4f5c5定理3网络N中的流f是最大流当且仅当N中不包含任何增广链例如下图中，s→v2→v1→v3→v4→t。Page24网络的最大流●stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(4)7(5)增广链：s→v2→v1→v3→v4→t。Page25网络的最大流对对,),(iiiffc对非增广链上的狐对对,,,'iiiffff结论：对于新的流f',仍然满足可行流条件，而且对s-t的流增大了一个θ值，因此只要途中找不到一个增广链时，s-t的流才不能进一步增大。定理3网络N中的流f是最大流当且仅当N中不包含任何增广链在增广链中做如下流的调整：Page26网络的最大流定理4在网络中s-t的最大流等于它的最小割集的容量，即),()(**VVcfv),()(),()(),(),(),()(),(),(),(),(),(),(*******),(),(*),(),(),(),(*VVcfvVVcfvVVcVVcVVffvijfVVfVVcjicjifVVfVVjiVVjiVVji则又Page27网络的最大流求网络最大流的标号算法：[基本思想]由一个流开始，系统地搜寻增广链，然后在此链上增流，继续这个增流过程，直至不存在增广链。[基本方法](1)找出第一个可行流，（例如所有弧的流量fij=0。）(2)用标号的方法找一条增广链首先给发点s标号(∞),标号中的数字表示允许的最大调整量。选择一个点vi已标号并且另一端未标号的弧沿着某条链向收点检查：Page28网络的最大流如果弧的起点为vi，并且有fijCij，则给vj标号为(Cij－fij)如果弧的方向指向vi，并且有fji0，则vj标号(fji)(3)重复第(2)步，可能出现两种结局：标号过程中断，t无法标号，说明网络中不存在增广链，目前流量为最大流。同时可以确定最小割集，记已标号的点集为V,未标号的点集合为V′,(V,V′)为网络的最小割。t得到标号，反向追踪在网络中找到一条从s到t得由标号点及相应的弧连接而成的增广链。继续第(4)步Page29网络的最大流所有非增广链上的弧对增广链上所有后向弧对增广链上所有前向弧ftftff)()((4)修改流量。设原图可行流为f，令得到网络上一个新的可行流f’。(5)擦除图上所有标号，重复(1)-(4)步，直到图中找不到任何增广链，计算结束。Page30网络的最大流例6.10用标号算法求下图中s→t的最大流量，并找出最小割。●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)Page31网络的最大流解：(1)先给s标号(∞)●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)(0,∞)Page32网络的最大流●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)(0,∞)(2)检查与s点相邻的未标号的点，因fs1cs1，故对v1标号=min{∞,cs1-fs1}=1,)1((s,1)Page33网络的最大流●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(6)(0,∞)(s,1)(2)检查与v1点相邻的未标号的点，因f13c13，故对v3标号=min{1,c13-f13}=min{1,6}=1)3((v1,1)Page34网络的最大流●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)(0,∞)(s,1)(3)检查与v3点相