数学建模最短路问题VIP

.,第11章最短路问题,1.问题的提出2.图论的基本概念3.最短路问题求解算法4.建模实例,.,1问题的提出,某学校行政部门u0经常有人到7个部门办事，希望在现有的道路网络中确定他们行走的路线，使他们到各部门的路程最短。图中已经标明了部门到部门之间的距离。,.,2图论的基本概念,图论是离散数学的重要分支，在物理学、化学、系统控制、电力通讯、编码理论、可靠性理论、科学管理、电子计算机等各个领域都具有极其广泛的应用。图论的历史可以追溯到1736年，这一年发表了图论的第一篇论文，解决了著名的哥尼斯堡（Knigsberg）七桥问题。,.,Knigsberg七桥问题,哥尼斯堡城中有七座桥将普雷格尔(Pregel)河中的两个岛与河岸联结起来，当时人们热衷于这样一个问题：一个人能否从四块陆地中的任何一块出发走过七座桥，每座桥恰走一次，最后回到起点？,(a),.,图论的基本概念,1.图的定义G=(V,E,)顶点，边，e与v连接，v与e关联，相邻，环，重边，平面图，完全图（完备图），二部图（偶图），子图，生成图。与一个顶点vi关联的边的数目称为vi的度（或次）。路、圈和连通有向图、赋权图,.,图论的一个定理,定理：d(v)=2|E|vV,证：因为每一条边提供给点的度为2，所以图中所有点的度数总和是边数的2倍。推论：在任何图中，奇点个数为偶数。,.,2.图的矩阵表示,对于任意图G，定义一个nm阶矩阵M=（mij）nm(n为顶点数，m为边数)，其中mij是vi和ej相关联的次数（0,1或2等），该矩阵称为G的关联矩阵。图的另一种表示形式是邻接矩阵A=（aij）nn，其中aij是连接ai和aj的边的数目。,.,图的矩阵表示,关联矩阵邻接矩阵,.,3最短路问题求解算法,设G为赋权有向图或无向图，G边上的权均非负。1.DijkstraAlgorithm:求G中从顶点u0到其余顶点的最短路。定义：对每个顶点v，定义两个标号l(v),z(v),其中l(v)为从u0到v的路长；z(v)为v的父亲点（前一个点）。S：具有永久标号的顶集。算法的过程就是在每一步改进这两个标号，最终l(v)为u0到v的最短路长。输入带权邻接矩阵（距离矩阵）w(u,v).,.,最短路问题求解算法,DijkstraAlgorithm,Dijkstra算法所需时间与n2成正比。,.,用Dijkstra求解最短路问题,例求从顶点u0到其余顶点的最短路。,解：先写出距离矩阵（实际应为对称矩阵）,Dijkstra算法的迭代步骤如下,迭代l(ui)次数u0u1u2u3u4u5u6u7,102218328104831058610126710127912812,最后标记：l(v)021736912z(v)u0u0u0u5u1u4u3u4,.,最短路问题求解算法,2.FloydAlgorithm(1962):求任意两点间的最短路。D=（dij）nn,dij是i到j的最短路长，P=（pij）nn,pij是i到j的最短路上中间节点的最大号码，pij=0，表示无中间节点，,(1)赋初值：dij=wij,pij=0,k=1(2)更新dij,pij：对所有i,j，若dik+dkj|M|，则称M为G的最大匹配。,.,匹配与覆盖,显然，完美匹配一定是最大匹配，反之不一定成立。(a)最大匹配(b)完美匹配,.,匹配与覆盖,定义2设若G的每条边都与K的一个顶点关联，则称K是图G的一个覆盖。设K是G的一个覆盖，若不存在覆K使|K|0），则G有完美匹配。,.,二部图的匹配,例：如果一个乡村里每位姑娘恰好认识k位小伙子，而每个小伙子也恰好认识k位姑娘，则每位姑娘能够和她认识的一个小伙子结婚，并且每个小伙子也能和他认识的一位姑娘结婚。此即为“婚姻定理”。根据上面的定理，Edmonds于1965年提出了如下的匈牙利算法，解决了二部图的基数匹配问题，步骤如下：,.,二部图的匹配,匈牙利算法：(1)设G=(X,Y,E)是二部图，M是一个匹配；(2)若M饱和X的每个顶点，则算法终止，M为最大匹配；否则，取M-非饱和点uX，令S=u,T=;(3)若N(S)=T,由于|T|=|S|-1，所以|N(S)|0,则称路P是f非饱和的，称P为可增路（增广路）,.,最大流基本定理,网络中f可增路P的存在意味着f不是最大流。可沿着P增加一个值为(P)的附加流量，得到由所定义的新可行流f，val(f)=val(f)+(P),称为基于P的调整流。,.,最大流基本定理,定理1N中的可行流f是最大流当且仅当N不包含f可增路。定理2在任何网络中，最大流的流量等于最小割的容量。,.,3Ford和Fulkerson标号算法,(1)置每个fij等于一个可行流f的对应值。若网络中没有给定f，则设f是零流。(2)给发点vs标上(0，+)，vs成为已标号而未检查的点，其它点为未标号点。(3)如果不存在已标号而未检查的点，算法终止，现行流即为最大流；否则按标号的先后次序取一个已标号而未检查的点vi，对一切未标号点vj，若弧(vi,vj)为非饱和弧，即fij0，则给vj以标号(vi，j)，其中j=mini,fji这时成为已标号而未检查的点。考虑完一切未标号点vj后，vi便成为已标号并检查过后点。,.,Ford和Fulkerson标号算法,(4)如果收点vt未标号，转(3)；否则转(5)。(5)从开始vt，通过第一标号，逆向找出可增路P，并令去掉所的点的标号，转(2)。,.,4最小费用最大流,上节我们已经求得石油运输管网的最大输油量为5桶/分钟。假设运输管网上各管道aij输送石油的单位流量的运费如下图所示，要确定这样一个方案，使输油量最大，同时使总的运输费用最小。,cij,bij,.,调整网络,对网络N的可行流定义调整容量的流网络N(f)如下：N与N有相同的顶点集合；对N的弧(vi,vj)，其上的流为fij，容量为cij，费用为bij，N中有两条弧(vi,vj)和(vj,vi)与之对应，弧(vi,vj)的容量为cij-fij，费用为bij；弧(vj,vi)的容量为fij，费用为-bij，再去掉所有容量为0的弧。由这个定义可知，N(f)中自vs到vt的一条有向路P(N)确定了中一条vs到vt的可增路。,.,5迭加算法,定理2设f1是N中流量为F的最小费用流，f2是N(f1)中沿最小费用的有向路P的单位流，则f1+f2是N中流量为F+1的最小费用流。,.,Ford和Fulkerson迭加算法,(1)给定目标流量