最短路问题 (2).ppt

《最短路问题 (2).ppt》由会员分享，可在线阅读，更多相关《最短路问题 (2).ppt（39页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、关于最短路问题(2)现在学习的是第1页，共39页数学建模与数学实验数学建模与数学实验 最短路问题最短路问题现在学习的是第2页，共39页实验目的实验目的实验内容实验内容2、会用、会用Matlab软件求最短路软件求最短路1、了解最短路的算法及其应用、了解最短路的算法及其应用1、图、图 论论 的的 基基 本本 概概 念念2、最、最 短短 路路 问问 题题 及及 其其 算算 法法3、最、最 短短 路路 的的 应应 用用4、建模案例：最优截断切割问题、建模案例：最优截断切割问题5、实验作业、实验作业现在学习的是第3页，共39页图图 论论 的的 基基 本本 概概 念念一、一、图图 的的 概概 念念1、图的

2、定义、图的定义2、顶点的次数、顶点的次数 3、子图、子图二、二、图图 的的 矩矩 阵阵 表表 示示1、关联矩阵关联矩阵2、邻接矩阵邻接矩阵返回返回现在学习的是第4页，共39页定义定义有序三元组G=(V,E,)称为一个图图.1 V=,21nvvv是有穷非空集，称为顶顶点点集集，其中的元素叫图 G 的顶顶点点.2 E 称为边边集集，其中的元素叫图 G 的边边.3 是从边集 E 到顶点集 V 中的有序或无序的元素 偶对的集合的映射，称为关关联联函函数数.例例1 设 G=(V,E,)，其中 V=v1,v2,v3,v4，E=e1,e2,e3,e4,e5,335414413312211)(,)(,)(,)

3、(,)(vvevvevvevvevve.G 的图解如图.图的定义图的定义现在学习的是第5页，共39页定义定义在图 G 中，与 V 中的有序偶(vi，vj)对应的边 e，称为图的有有向向边边（或弧），而与 V 中顶点的无序偶 vivj相对应的边 e，称为图的无无向向边边.每一条边都是无向边的图，叫无无向向图图；每一条边都是有向边的图，称为有有向向图图；既有无向边又有有向边的图称为混混合合图图.定义定义若将图 G 的每一条边 e 都对应一个实数 w(e)，称 w(e)为边的权权，并称图 G 为赋赋权权图图.规定用记号和分别表示图的顶点数和边数.现在学习的是第6页，共39页常用术语：（）端点相同的边

4、称为环环（）若一对顶点之间有两条以上的边联结，则这些边称为重边重边（）有边联结的两个顶点称为相邻的顶点相邻的顶点，有一个公共端点的边 称为相邻的边相邻的边（）边和它的端点称为互相关联关联的 （）既没有环也没有平行边的图，称为简单图简单图（）任意两顶点都相邻的简单图，称为完备图完备图，记为 Kn，其中 n 为顶点的数目(7)若 V=XY，XY=，X 中任两顶点不相邻，Y 中任两顶点不相邻，称 G 为二元图二元图；若 X 中每一顶点皆与 Y 中一切顶点相邻，称为完备二元图完备二元图，记为 Km,n，其中 m,n 分别为 X 与 Y 的顶点数目现在学习的是第7页，共39页返回返回现在学习的是第8页，

5、共39页顶点的次数顶点的次数定定义义（）在无向图中，与顶点 v 关联的边的数目（环算两次）称为 v的次次数数，记为 d(v)（）在有向图中，从顶点 v 引出的边的数目称为 v的出出度度，记为 d+(v)，从顶点 v引入的边的数目称为的入入度度，记为 d-(v)，d(v)=d+(v)+d-(v)称为 v的次数4)(4vd5)(3)(2)(444vdvdvd现在学习的是第9页，共39页定定理理)(2)()(GvdGVv推推论论任何图中奇次顶点的总数必为偶数例例 在一次聚会中，认识奇数个人的人数一定是偶数。返回返回现在学习的是第10页，共39页子图子图定定义义设图 G=(V,E,),G1=(V1,E

6、1,1)(1)若 V1V，E1E,且当 eE1时，1(e)=(e),则称 G1是 G 的子子图图特别的，若 V1=V，则 G1称为 G 的生生成成子子图图(2)设 V1V，且 V1，以 V1为顶点集、两个端点都在 V1中的图 G 的边为边集的图 G 的子图，称为 G 的由由 V1导导出出的的子子图图，记为 GV1.(3)设 E1E,且 E1,以 E1为边集,E1的端点集为顶点集的图 G 的子图,称为 G 的由由 E1导导出出的的子子图图,记为 GE1.GGv1,v4,v5Ge1,e2,e3返回返回现在学习的是第11页，共39页关联矩阵关联矩阵对无向图，其关联矩阵)(ijm，其中：不关联与若相关

7、联与若jijiijevevm01M=43215432110110011000101110001vvvveeeee对有向图，其关联矩阵)(ijm，其中：不关联与若的终点是若的起点是若jijijiijevevevm011注：假设图为简单图返回返回现在学习的是第12页，共39页邻接矩阵邻接矩阵对无向图，其邻接矩阵)(ijaA，其中：不相邻与若相邻与若jijiijvvvva01注：假设图为简单图A=432143210111101011011010vvvvvvvv对有向图（，），其邻接矩阵)(ijaA，其中：EvvEvvajijiij），若（），若（01现在学习的是第13页，共39页对有向赋权图，其邻接

8、矩阵)(ijaA，其中：EvvjiwEvvwajiijjiijij),(0,),(若若为其权且若无向赋权图的邻接矩阵可类似定义A=4321432105375083802720vvvvvvvv返回返回现在学习的是第14页，共39页最最 短短 路路 问问 题题 及及 其其 算算 法法一、一、基基 本本 概概 念念二、固二、固 定定 起起 点点 的的 最最 短短 路路三、每三、每 对对 顶顶 点点 之之 间间 的的 最最 短短 路路返回返回现在学习的是第15页，共39页基基 本本 概概 念念通路44112544141vevevevevWvv道路4332264521141vevevevevevTvv路

9、径4521141vevevPvv定定义义在无向图 G=(V,E,)中：（）顶点与边相互交错且iiivve1)(i=1,2,k)的有限非空序列)(12110kkkvevevevw称为一条从0v到kv的通通路路，记为kvvW0（）边不重复但顶点可重复的通路称为道道路路，记为kvvT0（）边与顶点均不重复的通路称为路路径径，记为kvvP0现在学习的是第16页，共39页定定义义（）任意两点均有路径的图称为连连通通图图（）起点与终点重合的路径称为圈圈（）连通而无圈的图称为树树定定义义（）设 P(u,v)是赋权图 G 中从 u 到 v 的路径，则称)()()(PEeewPw为路径 P 的权权(2)在赋权图

10、 G 中，从顶点 u 到顶点 v 的具有最小权的路 ),(*vuP，称为 u 到 v 的最最短短路路返回返回现在学习的是第17页，共39页固固 定定 起起 点点 的的 最最 短短 路路最短路是一条路径，且最短路的任一段也是最短路 假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树 因此,可采用树生长的过程来求指定顶点到其余顶点的最短路现在学习的是第18页，共39页设 G 为赋权有向图或无向图，G 边上的权均非负对每个顶点，定义两个标记（l v()，z v()），其中:l v()：表从顶点 u0到 v 的一条路的权 z v()：v 的父亲点，用以确定最短路的路

11、线算法的过程就是在每一步改进这两个标记，使最终l v()为从顶点u0到 v 的最短路的权S：具有永久标号的顶点集输入:G 的带权邻接矩阵),(vuw现在学习的是第19页，共39页算法步骤：算法步骤：（4）若S，转 2，否则，停止.用上述算法求出的l v()就是u0到v的最短路的权，从v的父亲标记)(vz追溯到u0,就得到u0到v的最短路的路线.现在学习的是第20页，共39页例例 求下图从顶点u1到其余顶点的最短路 TO MATLAB(road1)现在学习的是第21页，共39页)(iul迭代次数1u2u3u 4u5u6u 7u 8u2345678 0 2 8 10 8 3 10 8 6 10 1

12、2 7 1012 9 12 12最后标记:)(vl)(vz 0 2 1 7 3 6 9 12 1u 1u 1u 6u 2u 5u 4u 5u现在学习的是第22页，共39页)(iul1u2u3u 4u5u6u 7u 8u最后标记:)(vl)(vz 0 2 1 7 3 6 9 12 1u 1u 1u 6u 2u 5u 4u 5uu1u2u3u4u5u6u7u8返回返回现在学习的是第23页，共39页每每 对对 顶顶 点点 之之 间间 的的 最最 短短 路路(二二)算算法法原原理理1、求距离矩阵的方法、求距离矩阵的方法2、求路径矩阵的方法、求路径矩阵的方法3、查找最短路路径的方法、查找最短路路径的方法

13、（一）算法的基本思想（一）算法的基本思想（三）算法步骤（三）算法步骤返回返回现在学习的是第24页，共39页算法的基本思想算法的基本思想 直接在图的带权邻接矩阵中用插入顶点的方法依次构造出个矩阵 D(1)、D(2)、D()，使最后得到的矩阵 D()成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径返回返回现在学习的是第25页，共39页算法原理算法原理 求距离矩阵的方法求距离矩阵的方法把带权邻接矩阵 W 作为距离矩阵的初值，即 D(0)=)()0(ijd=W（）D(1)=)()1(ijd，其中)0(1)0()1(,miniijijddd)0(1jd)1(ijd是从 vi到 vj的只允许

14、以 v1作为中间点的路径中最短路的长度（2）D(2)=)()2(ijd，其中)1(2)1()2(,miniijijddd)1(2 jd )2(ijd是从 vi到 vj的只允许以 v1、v2作为中间点的路径中最短路的长度（）D()=)()(ijd，其中)1()1()(,miniijijddd)1(jd)(ijd是从 vi到 vj的只允许以 v1、v2、v作为中间点的路径中最短路的长度即是从 vi到 vj中间可插入任何顶点的路径中最短路的长，因此D()即是距离矩阵返回返回现在学习的是第26页，共39页算法原理算法原理 求路径矩阵的方法求路径矩阵的方法R=)(ijr,rij的含义是从 vi到 vj的

15、最短路要经过点号为 rij的点)()0()0(ijrR,jrij)0(每求得一个 D(k)时，按下列方式产生相应的新的 R(k)否则若)1()1()1()1()(kkjkikkijkijkijdddrkr在建立距离矩阵的同时可建立路径矩阵R 即当vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的路径)(D)(R)(R返回返回现在学习的是第27页，共39页ij算法原理算法原理 查找最短路路径的方法查找最短路路径的方法若1)(prij，则点 p1是点 i 到点 j 的最短路的中间点.然后用同样的方法再分头查找若：（）向点 i 追朔得：2)(1p

16、rip,3)(2prip,kipprk)(（）向点 j 追朔得：1)(1qrjp,2)(1qrjq,jrjqm)(pkp2p1p3q1q2qm则由点i到j的最短路的路径为：jqqqpppimk,21,12返回返回现在学习的是第28页，共39页算法步骤算法步骤Floyd算算法法：求任意两点间的最短路D(i,j)：i 到j 的距离R(i,j)：i 到j 之间的插入点输入:带权邻接矩阵 w(i,j)（）赋初值：对所有 i,j,d(i,j)w(i,j),r(i,j)j,k1(2)更新 d(i,j),r(i,j)对所有 i,j，若 d(i,k)+d(k,j)d(i,j)，则 d(i,j)d(i,k)+d

17、(k,j),r(i,j)k(3)若 k=，停止否则 kk+1，转（）现在学习的是第29页，共39页例例 求下图中加权图的任意两点间的距离与路径 TO MATLAB(road2(floyd)5333434331543243332344441,0646960243420256420793570RD951d，故从v5到v1的最短路为51r由 v4向 v5追朔：3,35354rr;由 v4向 v1追朔：141r所以从 v5到 v1的最短路径为：1435.返回返回现在学习的是第30页，共39页最最 短短 路路 的的 应应 用用一、一、可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题二、二

18、、选选 址址 问问 题题1、中心问题中心问题2、重心问题重心问题返回返回现在学习的是第31页，共39页可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题 例例 1 设备更新问题：企业使用一台设备，每年年初，企业领导就要确定是购置新的，还是继续使用旧的.若购置新设备，就要支付一定的购置费用；若继续使用，则需支付一定的维修费用.现要制定一个五年之内的设备更新计划，使得五年内总的支付费用最少.已知该种设备在每年年初的价格为：第一年第二年第三年第四年第五年1111121213 使用不同时间设备所需维修费为：使用年限0112233445维修费5681118现在学习的是第32页，共39页构造

19、加权有向图 G1(V,E)（1）顶点集 VXib,i=1,2,3,4,5Xirk(),i=2,3,4,5,6;k=1,2,i-1,每个顶点代表年初的一种决策，其中顶点Xib代表第 i 年初购置新设备的决策，顶点Xirk()代表第 i 年初修理用过 k 年的旧设备的决策现在学习的是第33页，共39页（2）弧集 E=(,),(,),(),XXXXibibirkib11i=1,2,3,4;k=1,2,i-1 (,),()XXibir11,i=1,2,3,4,5(,)(),()XXirkirk11,i=1,2,3,4,5;k=1,2,i-1若第 i 年初作了决策Xi后，第 i+1 年初可以作决策Xi1

20、，则顶点Xi与Xi1之间有弧(Xi,Xi1)，其权 W(Xi,Xi1)代表第 i 年初到第 i+1 年初之间的费 用.例如，弧(,)()XXbr341代表第 3 年初买新设 备，第四 年初决定用第三 年买的用 过一年的 旧设备，其权则为 第三年初 的购置费 与三、四年间 的维修费 之和，为 12517（3）问题转化为顶点Xb1到Xrk6()的最短路问题.五年的最优购置费为 kbrkd XX1 2 3 4 516,()min(,)其中 d(Xb1,Xrk6()为顶点Xb1到Xrk6()的最短路的权.求 得 最 短 路 的 权 为 53，而 两 条 最 短 路 分 别 为 XXXXXXbrrbrr

21、1213245162()()()();XXXXXXbrbrrr1213415263()()()()因 此，计 划 为 第 一、三 年 初 购 置 新 设 备，或 第 一、四 年 初 购 置 新 设 备，五 年 费 用 均 最 省，为 53.现在学习的是第34页，共39页也可构造加权有向图 G2(V,E).（1）顶点集 V=V V V V V V123456,，Vi表第 i 年初购置新设备的决策，V6表第五年底.（2）弧集 E=(,)V Vij，i=1,2,3,4,5;ij6,弧(,)V Vij表第 i 年初购进一台设备一直使用到第 j 年初的决策，其权 W(,)V Vij表由这一决策在第 i

22、年初到第 j 年初的总费用，如W(,)V V14=11+5+6+8=30.（3）问题转化为求V1到V6的最短路问题，求得两条最短路为VVV146，VVV136，权为 53，与图 G1(V,E)的解相同返回返回现在学习的是第35页，共39页（2）计算在各点iv设立服务设施的最大服务距离)(ivS max)(1ijjidvS ,2,1i 选址问题选址问题-中心问题中心问题例例 2某城市要建立一个消防站，为该市所属的七个区服务，如图所示问应设在那个区，才能使它至最远区的路径最短（1）用 Floyd 算法求出距离矩阵 D=)(ijd（3）求出顶点kv，使)(min)(1iikvSvS则kv就是要求的建

23、立消防站的地点此点称为图的中中心心点点 TO MATLAB(road3(floyd)现在学习的是第36页，共39页05.15.55.86475.10475.45.25.55.54032475.8730571065.42502545.24720375.5710530DS(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故应将消防站设在v3处。返回返回现在学习的是第37页，共39页 选址问题选址问题-重心问题重心问题例例 3某矿区有七个矿点，如图所示已知各矿点每天的产矿量)(jvq（标在图的各顶点上）现要从这七个矿点选一个来建造矿厂 问应选在哪个矿点，才能使各矿点所产的矿运到选矿厂所在地的总运力（千吨公里）最小（1）求距离阵 D=)(ijd（2）计算各顶点作为选矿厂的总运力)(ivm ijjjidvqvm)()(1 ,2,1i（3）求kv使)(min)(1iikvmvm，则kv就是选矿厂应设之矿点此点称为图 G 的重重心心或中中位位点点返回返回现在学习的是第38页，共39页感谢大家观看感谢大家观看现在学习的是第39页，共39页