数学建模最短路问题课件

1、第11章 最短路问题,1. 问题的提出 2. 图论的基本概念 3. 最短路问题求解算法 4. 建模实例,1,学习交流PPT,1 问题的提出,某学校行政部门u0经常有人到7个部门办事，希望在现有的道路网络中确定他们行走的路线，使他们到各部门的路程最短。 图中已经标明了部门到部门之间的距离。,2,学习交流PPT,2 图论的基本概念,图论是离散数学的重要分支，在物理学、化学、系统控制、电力通讯、编码理论、可靠性理论、科学管理、电子计算机等各个领域都具有极其广泛的应用。 图论的历史可以追溯到1736年，这一年发表了图论的第一篇论文，解决了著名的哥尼斯堡（Knigsberg）七桥问题。,3,学习交流PP

2、T,Knigsberg七桥问题,哥尼斯堡城中有七座桥将普雷格尔(Pregel)河中的两个岛与河岸联结起来，当时人们热衷于这样一个问题：一个人能否从四块陆地中的任何一块出发走过七座桥，每座桥恰走一次，最后回到起点？,(a),4,学习交流PPT,图论的基本概念,1. 图的定义 G=(V, E,) 顶点，边，e与v连接，v与e关联，相邻，环，重边，平面图，完全图（完备图），二部图（偶图），子图，生成图。 与一个顶点vi关联的边的数目称为vi的度（或次）。 路、圈和连通 有向图、赋权图,5,学习交流PPT,图论的一个定理,定理：d(v)=2|E| vV,证：因为每一条边提供给点的度为2，所以图中所有点

3、的度数总和是边数的2倍。 推论：在任何图中，奇点个数为偶数。,6,学习交流PPT,2. 图的矩阵表示,对于任意图G，定义一个nm阶矩阵M=（mij）nm(n为顶点数，m为边数)，其中mij是vi和ej相关联的次数（0, 1或2等），该矩阵称为G的关联矩阵。 图的另一种表示形式是邻接矩阵A=（aij）nn，其中aij是连接ai和aj的边的数目。,7,学习交流PPT,图的矩阵表示,关联矩阵 邻接矩阵,8,学习交流PPT,3最短路问题求解算法,设G为赋权有向图或无向图，G边上的权均非负。 1. Dijkstra Algorithm: 求G中从顶点u0到其余顶点的最短路。 定义： 对每个顶点v，定义两

4、个标号l(v), z(v), 其中l(v)为从u0到v的路长； z(v)为v的父亲点（前一个点）。 S：具有永久标号的顶集。 算法的过程就是在每一步改进这两个标号，最终l(v)为u0到v的最短路长。输入带权邻接矩阵（距离矩阵）w(u, v).,9,学习交流PPT,最短路问题求解算法,Dijkstra Algorithm,Dijkstra算法所需时间与n2成正比。,10,学习交流PPT,用Dijkstra求解最短路问题,例 求从顶点u0到其余顶点的最短路。,解：先写出距离矩阵（实际应为对称矩阵）,11,学习交流PPT,Dijkstra算法的迭代步骤如下,迭代 l(ui) 次数 u0 u1 u2

5、u3 u4 u5 u6 u7,1 0 2 2 1 8 3 2 8 10 4 8 3 10 5 8 6 10 12 6 7 10 12 7 9 12 8 12,最后标记： l(v) 0 2 1 7 3 6 9 12 z(v)u0 u0 u0 u5 u1 u4 u3 u4,12,学习交流PPT,最短路问题求解算法,2. Floyd Algorithm (1962): 求任意两点间的最短路。 D =（dij）nn, dij是i到j的最短路长， P =（pij）nn, pij是i到j的最短路上中间节点的最大号码，pij=0，表示无中间节点，,(1)赋初值：dij= wij, pij = 0, k =

6、1 (2)更新dij, pij：对所有i, j，若dik+dkj|M|，则称M为G的最大匹配。,19,学习交流PPT,匹配与覆盖,显然，完美匹配一定是最大匹配，反之不一定成立。 (a)最大匹配 (b)完美匹配,20,学习交流PPT,匹配与覆盖,定义2 设若G的每条边都与K的一个顶点关联，则称K是图G的一个覆盖。设K是G的一个覆盖，若不存在覆K使|K|0），则G有完美匹配。,24,学习交流PPT,二部图的匹配,例：如果一个乡村里每位姑娘恰好认识k位小伙子，而每个小伙子也恰好认识k位姑娘，则每位姑娘能够和她认识的一个小伙子结婚，并且每个小伙子也能和他认识的一位姑娘结婚。此即为“婚姻定理”。 根据上

7、面的定理，Edmonds于1965年提出了如下的匈牙利算法，解决了二部图的基数匹配问题，步骤如下：,25,学习交流PPT,二部图的匹配,匈牙利算法： (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为可增路（增广路）,62,学习交流PPT,最大流基本定理,网络中f可增路P的存在意味着f不是最大流。可沿着P增加一个值为(P)的附加流量，得到由 所定义的新可行流f，val(f)=val(f)+ (P

8、), 称为基于P的调整流。,63,学习交流PPT,最大流基本定理,定理1 N中的可行流f是最大流当且仅当N不包含f可增路。 定理2 在任何网络中，最大流的流量等于最小割的容量。,64,学习交流PPT,3Ford和Fulkerson标号算法,(1)置每个fij等于一个可行流f的对应值。若网络中没有给定f，则设f是零流。 (2)给发点vs标上(0，+)，vs成为已标号而未检查的点，其它点为未标号点。 (3)如果不存在已标号而未检查的点，算法终止，现行流即为最大流；否则按标号的先后次序取一个已标号而未检查的点vi，对一切未标号点vj，若弧(vi,vj)为非饱和弧，即fij0，则给vj以标号(vi，j

9、)，其中j=mini, fji 这时成为已标号而未检查的点。 考虑完一切未标号点vj后，vi便成为已标号并检查过后点。,65,学习交流PPT,Ford和Fulkerson标号算法,(4)如果收点vt未标号，转(3)；否则转(5)。 (5)从开始vt，通过第一标号，逆向找出可增路P，并令 去掉所的点的标号，转(2)。,66,学习交流PPT,4最小费用最大流,上节我们已经求得石油运输管网的最大输油量为5桶/分钟。假设运输管网上各管道aij输送石油的单位流量的运费如下图所示，要确定这样一个方案，使输油量最大，同时使总的运输费用最小。,cij, bij,67,学习交流PPT,调整网络,对网络N的可行流

10、定义调整容量的流网络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的可增路。,68,学习交流PPT,5迭加算法,定理2 设f1是N中流量为F的最小费用流，f2是N(f1)中沿最小费用的有向路P的单位流，则f1+ f2是N中流量为F+1的最小费用流。,69,学习交流PPT,Ford和Fulkerson迭加算法,(1)给