应用一：最短路问题

1、数学建模数学建模图论方法专题图论方法专题 最最 短短 路路 问问 题题 它不仅它不仅可以直接应用于解决生产实际的许多问题可以直接应用于解决生产实际的许多问题而且经常被作为一个基本工具，用于解决而且经常被作为一个基本工具，用于解决其它优化问题如其它优化问题如v定义定义：设设P(u,v)是加权图是加权图G中从中从u到到v的路径的路径,则该路则该路径上的边权之和称为该路径的权径上的边权之和称为该路径的权,记为记为w(P). 从从u到到v的路径中权最小者的路径中权最小者 P*(u,v)称为称为u到到v的的.v最短路问题在实际工作中应用最短路问题在实际工作中应用u1、通讯网络中最可靠问题、通讯网络中最可

2、靠问题u2、最大容量问题、最大容量问题u3、统筹方法中求关键路线、统筹方法中求关键路线u4、背包问题、背包问题u5、选址问题、选址问题u6、工件加工顺序问题、工件加工顺序问题u7、中国邮递员问题、中国邮递员问题若若v0 v1 vm 是是G中从中从v0到到vm的最短路的最短路, 则对则对1km, v0v1 vk 必为必为G中从中从v0到到vk的最短路的最短路. 即：最短路是一条路，且最短路的任一段也是最短路。即：最短路是一条路，且最短路的任一段也是最短路。vDijkstra算法算法 Dijkstra算法是由荷兰计算机科学家狄克斯特拉算法是由荷兰计算机科学家狄克斯特拉（Dijkstra）于）于19

3、59 年提出的。年提出的。1)寻求从一固定顶点寻求从一固定顶点v0到其余各点的最短路径到其余各点的最短路径;2)有向图、无向图和混合图有向图、无向图和混合图;3)权非负权非负.：从始点出发，逐步从始点出发，逐步顺序地向外探寻顺序地向外探寻，每向外延伸一步都要求每向外延伸一步都要求是是 算法步骤算法步骤S: 具有永久标号的顶点集具有永久标号的顶点集;l(v): v的标记的标记,表示从起点表示从起点v0到到v的一条路的权的一条路的权; z(v):v的父顶点的父顶点,用以确定最短路径用以确定最短路径; 两种标号两种标号 P 标号标号（Permanent固定固定/永久性标号）永久性标号） 从始点到该标

4、号点的最短路权从始点到该标号点的最短路权 T 标号标号（Temporary临时性标号）临时性标号） 从始点到该标号点的最短路权从始点到该标号点的最短路权输入加权图的带权邻接矩阵输入加权图的带权邻接矩阵w=w(vi,vj)nxn.1)初始化：令初始化：令l(v0)=0, （给起始点给起始点v0标上固定标号标上固定标号） , v v0 ,l(v)= （其余各点标临时性标号其余各点标临时性标号 ）; S=v0; z(v)=v02)更新更新l(v), z(v) 寻找不在寻找不在S中的顶点中的顶点u（与前一点相邻接）（与前一点相邻接）,使使l(u)为最小为最小.把把u加入到加入到S中中,然后对所有不在然

5、后对所有不在S中的顶点中的顶点v,如如l(v)l(u)+w(u,v),则则更新更新l(v),z(v), 即即 l(v)l(u)+w(u,v),z(v)u;3)重复步骤重复步骤2), 直到所有顶点都在直到所有顶点都在S中为止中为止.例例1： 用用Dijkstra算法求下图从算法求下图从v1到到v6的最短路。的最短路。 v1v2v3v4v6v5352242421 解解 （1）首先给）首先给v1以以P标号，给其余所有点标号，给其余所有点T标号。标号。0)(1 vP)6,3,2()( ivTi（2）330,min)(, )(min)(12122 lvPvTvT550,min)(, )(min)(131

6、33 lvPvTvT23456222min ()min (), (), (), (), ()()3,()3()1jjvsT vT vT vT vT vT vT vp vz v所以有，1vS 21vvS， v1的邻接点为的邻接点为v2 ，v3 。v1v2v3v4v6v5352242421（4）413,5min)(, )(min)(23233 lvPvTvT523,min)(, )(min)(24244 lvPvTvT523,min)(, )(min)(25255 lvPvTvT2)(4)(, 4)()(),(),(),(min)(min3336543 vfvpvTvTvTvTvTvTjsvj，所

7、以有，所以有，例例1： 用用Dijkstra算法求下图从算法求下图从v1到到v6的最短路。的最短路。 v2的邻接点为的邻接点为v3 ，v4 ，v5 。321vvvS， v1v2v3v4v6v5352242421（5）；544,5min)(, )(min)(35355 lvPvTvT725, 45,min)(,)(, )(min)(56546466 lvPlvPvTvT（6）反向追踪得反向追踪得v1到到v6的最短路为：的最短路为：6521vvvv5)(, 5)(, 5)()()(),(),(min)(min5454654 vpvpvTvTvTvTvTvTjsvj所以有，所以有，5)(7)(, 7

8、)(min)(min666 vfvpvTvTjsvj，所以有，所以有，v3的邻接点为的邻接点为v5 。2)()(5454321 vfvfvvvvvS；，1,6例例2：v5v223464v3v1v41210 6 1210v8v9v72363v60,01, 1, 1,11, 1, 1, 1,31,6v5v223464v3v1v41210 6 1210v8v9v72363v60,01, 1, 1,11, 1, 1, 1,31,6v5v223464v3v1v41210 6 1210v8v9v72363v60,01, 4,111,11, 1, 1, 1,31,5v5v223464v3v1v41210 6

9、 1210v8v9v72363v60,01, 4,111,11, 1, 1, 1,31,61,5v5v223464v3v1v41210 6 1210v8v9v72363v60,01, 4,111,11, 1, 1, 1,33,53,5v5v223464v3v1v41210 6 1210v8v9v72363v60,01, 4,111,11, 1, 1,31, 3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,01, 4,111,11, 1, 1,31, 3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,04,111,11,

10、2,61, 1,31,3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,04,111,11, 2,61, 1,31,3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,05,101,11, 2,65,121,35,93,5v5v223464v3v1v41210 6 1210v8v9v72363v60,05,101,11, 2,65,121,35,9 知从知从v1到到v8 的最短路为：的最短路为： P1，8=P（v1，v3 ， v2， v5，v8）w= 0 1 2 inf 7 4 8 inf; 1 0 2 3 inf inf

11、7 inf; 2 2 0 1 5 inf inf inf; inf 3 1 0 3 inf inf 6; 7 inf 5 3 0 3 inf 4; 4 inf inf inf 3 0 2 6; 8 7 inf inf inf 2 0 4; inf inf inf 6 4 6 4 0l = 0 1 2 3 6 4 6 9z = 1 1 1 3 4 1 6 40v2v1v3v4v5v1445642537w= 0 4 1 inf inf inf; inf 0 inf 4 2 4; inf 5 0 inf 6 7; inf inf inf 0 inf inf; inf inf inf 5 0 inf;

12、 inf inf inf inf 3 0;l = 0 4 1 8 6 8 6 9z = 1 1 1 2 2 3 6 4z 使用范围使用范围:1)求每对顶点的最短路径求每对顶点的最短路径;2)有向图、无向图和混合图有向图、无向图和混合图;z 算法思想算法思想: 直接在图的带权邻接矩阵中用插入顶点的方法依次递推直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出地构造出n个矩阵个矩阵D(1), D(2), , D(v), D(v)是图的距离矩阵是图的距离矩阵, 同时引入一个后继点矩阵记录两点间的最短路径同时引入一个后继点矩阵记录两点间的最短路径.z 输入参数：输入参数：G的带权邻接矩阵的带权邻

13、接矩阵W.z 算法输出：距离矩阵算法输出：距离矩阵D以及路由矩阵以及路由矩阵R.（I）求距离矩阵的方法）求距离矩阵的方法.（II）求路径矩阵的方法）求路径矩阵的方法.在建立距离矩阵的同时可建立路径矩阵在建立距离矩阵的同时可建立路径矩阵R ivjv（III）查找最短路路径的方法）查找最短路路径的方法.然后用同样的方法再分头查找若：然后用同样的方法再分头查找若：1av2av3avkav1bv2bvmbv（IV）Floyd算法：求任意两顶点间的最短路算法：求任意两顶点间的最短路.例例3： 求下图中加权图的任意两点间的距离与路径求下图中加权图的任意两点间的距离与路径. ,053142503330212

14、044401210 )0(D,654321654321654321654321654321654321 )0(R,053142503330212044401210 )0(D,min) 1() 1() 1()(kkjkikkijkijdddd插入点插入点 v1，得：得：,053132503330212043401210)1(D,654311654321654321654321154321654321 )1(R矩阵中带矩阵中带“=”的项为经迭代比较以后有变化的元素的项为经迭代比较以后有变化的元素.,min) 1() 1() 1()(kkjkikkijkijdddd插入点插入点 v2，得：得：,05

15、3132503330212043401210)1(D矩阵中带矩阵中带“=”的项为经迭代比较以后有变化的元素的项为经迭代比较以后有变化的元素.,05313250333021204534012510)2(D,654311654321654321654322154321654221 )2(R,min) 1() 1() 1()(kkjkikkijkijdddd,053132503330267120453640127510)3(D,654311654321654333654322153321653221 )3(R插入点插入点 v3，得：得：,05313250333021204534012510)2(D,

16、min) 1() 1() 1()(kkjkikkijkijdddd,053132503330267120453640127510)3(D插入点插入点 v4，得：得：,05313250359103302671520453964012107510)4(D,654311654444654333644322143321643221 )4(R,)4()5(DD插入点插入点 v5，得：得：,)4()5(RR,min) 1() 1() 1()(kkjkikkijkijdddd插入点插入点 v6，得：得：,05313250359103302671520453964012107510)5(D,053132503

17、587330265152043386401275310)6(D.654311654466654336644326163321666621 )6(R,053132503587330265152043386401275310)6(D.654311654466654336644326163321666621 )6(R8)6(52d8)6(52d故从故从v5到到v2的最短路为的最短路为8 6)6(52R由由v6向向v5追溯追溯: . 6)6(56R由由v6向向v2追溯追溯: , 1)6(62R. 2)6(12R所以从到的最短路径为：所以从到的最短路径为： .2165vvvva=0 1 inf inf

18、inf 2; 1 0 4 inf inf 4; inf 4 0 2 inf 1; inf inf 2 0 3 3; inf inf inf 3 0 5; 2 4 1 3 5 0;1v3v2v4v5v68523374a=0 8 6 2 inf; inf 0 -5 -3 inf; inf inf 0 inf 4; inf inf inf 0 inf; inf 3 inf 7 0; 最最 短短 路路 应用应用 例：某企业使用一种设备，在每年年初，决策者需要决定是否例：某企业使用一种设备，在每年年初，决策者需要决定是否购置新的，还是继续使用旧的。若购置新设备，就要支付一定购置新的，还是继续使用旧的。若

19、购置新设备，就要支付一定的购置费用；若继续使用旧的，需要支付一定的维修费用。现的购置费用；若继续使用旧的，需要支付一定的维修费用。现在的问题是如何制定一个五年计划，使总的支付费用最少，表在的问题是如何制定一个五年计划，使总的支付费用最少，表1为设备在各年年初的价格，表为设备在各年年初的价格，表2为使用不同时间的设备所需要的为使用不同时间的设备所需要的维修费用。维修费用。表表1 设备的各年价格设备的各年价格表表2 使用不同时间的维修费用使用不同时间的维修费用年份年份 一一 二二 三三 四四 五五购 置 费购 置 费 11 11 12 12 13使用年限使用年限 01 12 23 34 45年修理

20、费年修理费 5 6 8 11 18解：（解：（1）分析：显然可以选择的设备更新方案是很多的。例）分析：显然可以选择的设备更新方案是很多的。例如每年都更新一台新设备，其购置费用为（如每年都更新一台新设备，其购置费用为（11+11+12+12+13）万元万元=59万元，而每年支付的维修费用为万元，而每年支付的维修费用为5万元，五年的合计万元，五年的合计为为25万元，于是五年的支付费用为（万元，于是五年的支付费用为（59+25）=84万元。万元。 又如可决定在第一，三，五年各购置一台，这个方案的设又如可决定在第一，三，五年各购置一台，这个方案的设备购置费用为（备购置费用为（11+12+13）=36万

21、元，维修费用为万元，维修费用为（5+6+5+6+5）=27万元，五年总费用为万元，五年总费用为63万元。万元。 如何制定计划适得总的支付费用最少呢？可以把此问题如何制定计划适得总的支付费用最少呢？可以把此问题最化为最短路问题。最化为最短路问题。 （2）用点）用点v vi i 代表代表“第第i年年初购进一台新设备年年初购进一台新设备”这种状态（这种状态（v v6为第为第5年年年年底的末状态）。弧底的末状态）。弧（v vi i ,v vj j） 表示第表示第i年年初购进的设备一直使用到第年年初购进的设备一直使用到第j年年年年初。弧（初。弧（vi ,vj）上的权数表示该期间设备所需的费用）上的权数表

22、示该期间设备所需的费用. 每条弧的权可按已知资料计算出来。如（每条弧的权可按已知资料计算出来。如（v v1，v v4）是第一年年初购进的）是第一年年初购进的一台设备（支付购置费用为本一台设备（支付购置费用为本11万元），一直使用到了第万元），一直使用到了第3年年底（支付年年底（支付维修费用为维修费用为5+6+8=19万元），故弧（万元），故弧（v v1，v v4）权重为）权重为30万元。万元。 这样一来，制定一个最优更新计划的问题就等价于寻求从这样一来，制定一个最优更新计划的问题就等价于寻求从V1到到V6的最的最短路问题。短路问题。 按求最短路的计算方法（按求最短路的计算方法（V1，V3，V6

23、）及（）及（V1，V4，V6）均为最短路）均为最短路线，权重为线，权重为53万元。万元。v1v2v3v4 v5 v61616171718223041592230412331231、中心问题、中心问题所谓中心选址问题就是在一网络中选择一所谓中心选址问题就是在一网络中选择一点，建立点，建立公用服务设施公用服务设施，为该网络中的点，为该网络中的点提供服务，使得服务效率最高。比如一个提供服务，使得服务效率最高。比如一个区域的消防站、自来水厂、学校、变电站、区域的消防站、自来水厂、学校、变电站、银行、商店等选址。为了提高服务效率，银行、商店等选址。为了提高服务效率，自然的想法是将这些设施建立在中心地点。

24、自然的想法是将这些设施建立在中心地点。要求要求网络中最远的被服务点离服务设施的网络中最远的被服务点离服务设施的距离尽可能小距离尽可能小。ijnjidMaxvd 1)()(1inivdMinI Ivdk )(), 2 , 1()(1nidvhnjiji )()(1inikvhMinvh 设网络设网络N有个有个n点点v1,v2,vn。dij表示点表示点vi到到vj之间的距之间的距离（即最短路的长度），并记离（即最短路的长度），并记dii=0(i=1,2,n)。定义定义1: 记记 , 。若。若 ,则称点则称点vk为网络为网络N的中心，的中心，I为直径。为直径。定义定义2: 令令 ，若，若 ，则称，则

25、称vk为网络为网络N的中心。的中心。例例1某城市要建立一个消防站，为该市所某城市要建立一个消防站，为该市所属的七个区服务，如图所示问应设在哪个属的七个区服务，如图所示问应设在哪个区，才能使它至最远区的路径最区，才能使它至最远区的路径最 距离矩阵第距离矩阵第i行的最大值行的最大值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

26、,故应将消防站设在v3处. 例例2 教育部门打算在某新建城区建一所学教育部门打算在某新建城区建一所学校，让附近七个居民区的学生就近入学。校，让附近七个居民区的学生就近入学。七个居民区之间的道路如下图所示，学校七个居民区之间的道路如下图所示，学校应建在哪个居民区，才能使大家都方便？应建在哪个居民区，才能使大家都方便？（图中距离单位：百米）。（图中距离单位：百米）。2、重心问题、重心问题例例3 例例2中，七个居民区的学生人数分别为：中，七个居民区的学生人数分别为：40、25、45、30、20、35、50人，学校应人，学校应建在哪个居民区，才能使大家都方便？建在哪个居民区，才能使大家都方便？（图中距

27、离单位：百米）。（图中距离单位：百米）。某合同战术训练基地为保障即将进行的联合军事演某合同战术训练基地为保障即将进行的联合军事演习，准备在原有的习，准备在原有的1个油库的基础上，再设立个油库的基础上，再设立7个固个固定的燃料补给点。定的燃料补给点。v1v7v6v2v8v5v3v4油库与补给点的位置如图所示，其中油库位于油库与补给点的位置如图所示，其中油库位于v1点，点，补给点位于补给点位于v2, , v8点。点。经过前期的测绘工作，如果在油库和补给点之间修建经过前期的测绘工作，如果在油库和补给点之间修建简易公路，由于地形不同，每段公路花费如图，每单简易公路，由于地形不同，每段公路花费如图，每单

28、位费用为位费用为1万元。请根据测绘结果，规划一个总造价万元。请根据测绘结果，规划一个总造价最低的建设方案。最低的建设方案。v1v7v6v2v8v5v3v425734326436174182总造价最低总造价最低各补给点到油库的各补给点到油库的花费均达到最小花费均达到最小？v1v7 6v6 4 4v2 1 1v8 9v5 6v3 2 2 v4 32243611简易公路建设方案简易公路建设方案如图的交通网络，每条弧上的数字代表车辆在该路段行驶所需如图的交通网络，每条弧上的数字代表车辆在该路段行驶所需的时间，有向边表示单行道，无向边表示可双向行驶。若有一的时间，有向边表示单行道，无向边表示可双向行驶。

29、若有一批货物要从批货物要从1号顶点运往号顶点运往11号顶点，问运货车应沿哪条线路行驶，号顶点，问运货车应沿哪条线路行驶，才能最快地到达目的地？才能最快地到达目的地？ 102374116598118 9 10 11某公司在六个城市某公司在六个城市c1, ,c6中有分公司，从中有分公司，从ci到到cj的直接航程票价记在下述矩阵中的的直接航程票价记在下述矩阵中的 (i,j) 位置上。（位置上。（表示无直接航路），请帮助该公司设计一张任意两城表示无直接航路），请帮助该公司设计一张任意两城市间的票价最便宜的路线表。市间的票价最便宜的路线表。 055252510550102025251001020402010015252015050102540500已知一个地区的交通网络如下：其中