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