《运筹学最短路邮递员问题》由会员分享，可在线阅读，更多相关《运筹学最短路邮递员问题（118页珍藏版）》请在金锄头文库上搜索。
1、最短路问题 最短路问题是最重要的优化问题之一，它不仅可以直接应用于解决生产实际的许多问题例如各种管道的铺设、线路的安排、厂区的布局、设备的更新等等，而且经常被作为一个基本工具，用于解决其它优化问题如运输网络的最小费用流等。 （最短距离、费时最少、费用最省）,定义（权、赋权图）：对图G的每一条边e，可赋与一个实数 w（e）称为边e的权。图G连同它边上的权称为赋权图。路中边权最小的称为最短路。 权可以表示铁路长度，通讯网络的造价，网络中表示耗时等。,狄克斯拉（Dijkstra）算法,最短路问题可以化为线性规划问题求解，也可以用动态规划方法求解，这里介绍一种有效算法狄克斯拉（Dijkstra）算法，
2、这一算法是1959年首次被提出来的。该算法适用于每条弧的权数ij 0情形。算法的基本思路：从发点vs 出发，有一个假想的流沿网络一切可能的方向等速前进，遇到新节点后，再继续沿一切可能的方向继续前进，则最先到达终点vt 的流所走过的路径一定是最短的。为了实现这一想法，对假想流依次到达的点，依次给予p标号，表示vs到这些点的最短距离。对于假想流尚未到达的点给予T标号，表示vs到这些点的最短距离的估计值。具体作法如下： 1标p（vs）=0，其余点标T（vi）=+; 2由刚刚获得p标号的vi 点出发，改善它的相邻点vj 的T标号,即 新的T（vj）=min老的T（vj），p（vi）+ ij 若T（vj
3、）= p（vi）+ ij ，则记k（vj ）=vi（前点标记）; 3找出具有最小T标号的点，将其标号改为p标号。若vt 已获得p标号，则已找到最短路，由k（vt）反向追踪，就可找出vs 到vt 的最短路径，p（vt）就是vs 到vt 的最短距离。否则，转2。,例 求图中v1 到v8 的最短路。,v4,v2,3,2,6,5,v3,v5,v6,v7,v8,6,3,5,5,2,1,1,1,4,7,9,解：标p（v1）=0，其余点标T（vi）=+，i=2,3,4,5,6,7,8; T（v2）=min+,0+3=3, k（v2 ）=v1 T（v3）=min+,0+5=5, k（v3 ）=v1 T（v4）
4、=min+,0+6=6, k（v2 ）=v1 将具有最小T标号的v2 点的标号改为p标号：p（v2）=3； T（v3）=min5,3+1=4, k（v3 ）=v2 T（v5）=min+,3+7=10, k（v5 ）=v2 T（v6）=min+,3+4=7, k（v6 ）=v2 目前，点v3 具有最小T标号，将其标号改为p标号： p（v3）=4；,v1,v4,v2,3,2,6,5,v3,v5,v6,v7,v8,6,3,5,2,1,1,1,4,9,v1,7,p（v1）=0,p（v2）=3,p（v3）=4,T（v4）=min6,4+1=5, k（v4 ）=v3 T（v6）=min7,4+2=6, k
5、（v6 ）=v3,目前，点v4 具有最小T标号，将其标号改为p标号： p（v4）=5； T（v6）=min6,5+3=6; T（v7）=min+,5+5=10, k（v7 ）=v4,目前，点v6 具有最小T标号，将其标号改为p标号： p（v6）=6； T（v5）=min10,6+2=8, k（v5 ）=v6 T（v7）=min10,6+1=7, k（v7 ）=v6 T（v8）=min+,6+9=15, k（v8）=v6,5,目前，点v7 具有最小T标号，将其标号改为p标号： p（v7）=7； T（v8）=min15,7+5=12, k（v8）=v7 ; p（v5）=8； T（v8）=min12
6、,8+6=12, p（v8）=12；反向追踪找最短路径。,最短路径为：v1v2v3v6v7v8 ； 因p（v8）=12，所以v1v8 的最短距离为12。 最短路问题不仅可以求解交通图中两点之间的最短距离，实际中很多问题也可变为最短路问题加以求解。例如设备更新问题，厂区合理布局问题等。兹举一例： 例1（设备更新问题）某企业使用一台设备，在每年年底，企业都要决策下年度是购买一台新设备呢？还是继续使用这台设备。若购买新的，就要支付一笔购置费；如果使用旧设备，只要支付维修费，而维修费随着设备的使用年限延长而增加。现根据以往统计资料已经估算出设备在各年初的价格和不同使用年限的修理费用，分别如表1、表2所
7、示。 试确定一个五年内的设备更新计划，使五年内总支出最小。,图上标示法 下面我们结合例3介绍求解最短路问题的图上标示法，它比狄克斯拉算法更简洁。,表1,表2,解：先根据表1、表2的数据画出设备更新费用网络图，如下图所示。图中点vi 表示第i 年开始，弧（vi ,vj）表示设备第i 年初使用到第j 年初，弧（vi ,vj）上的权数表示该期间设备所需的费用。这样，求五年内设备最优更新方案便转化为求v1v6 的 最短路。,v1,v2,v3,v4,v5,v6,16,16,17,17,18,22,30,41,59,22,30,41,23,31,23,设d（vi）表示点vi 到终点的最短距离，根据动态规划
8、最优性原理，最短路径中任何子路径也必然是最短的。因此有 d（vi）=minij +d（vj） 注意，上式要对以vi 为起点的所有弧（vi ,vj）进行计算。然后将计,j,算结果直接标在图中点vi 的旁边，同时标出与点vi 最近的邻接点。 先从点v5 算起，逆向进行。,v1,v2,v3,v4,v5,v6,16,16,17,17,18,22,30,41,59,22,30,23,23,41,对于点v5 ：d（v5）=18，v5 v6 ；,18 v5 v6,对于点v4 ：d（v4）=min17+18,23=23，v4 v6 ；,23 v4 v6,对于点v3 ：d（v3）=min17+23,23+18,
9、31=31，v3 v6 ；,31,31 v3 v6,对于点v2 ：d（v2）=min16+31,22+23,30+18,41=41，v2v6 ；,41 v2 v6,对于点v1 ：d（v1）=min16+41,22+31,30+23,41+18,59=53,v1v3；或v1 v4。,53 v1 v3v6 或 v1 v4v6,10,9,6,3,1,7,0,2,11,5,13,2,8,6,1,7,2,2,2,9,1,5,1,1,9,1,4,3,9,7,4,6,3,10,9,6,3,1,7,0,2,11,5,13,2,8,6,1,7,2,2,2,9,1,5,1,1,9,1,4,3,9,7,4,6,3,
10、从一点到任意点的最短路,木器厂有六个车间，办事员经常要到各个车间了解生产进度。从办公室到各车间的路线由图1给出。,找出点1（办公室）到其它各点（车间）的最短路,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,距离、价格,边eij或记为（vi，vj）,点（vi）,权wij(dij),表示网络图形的特点,1、与欧氏几何的区别为，图中线的长短并不能表示真实的长度。 2、与地图的区别为两点之间的距离并不真实。,表示网络图形的特点,网络（图论）中两点之间的距离由两点间的边上的权来表示。（可由图中的点1、2与点1、3之间的关系来看）。,求网络上的一点到其它点 的最短路,Dijk
11、stra算法 图示,Dinkstra标号法,这是解决网络中某一点到其它点的最短路问题时目前认为的最好方法。 在这个问题中我们讨论的是从网络中的点1到其它各点的最短路。,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,从点1出发，因L11=0，在点1处标记,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,从已标号的点出发，找与这些相邻点最小权数（距离）者，找到之后：标号；边变红。,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1
12、,0,2,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,从已标号的点出发，找与这些相邻点最小权数（距离）者，找到之后：标号；边变红。,2,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,从已标号的点出发，找与这些相邻点最小权数（距离）者，找到之后：标号；边变红。,2,3,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,重复上述步骤，直至全部的点都标完。,2,3,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,重复上述步骤，直至全部的点都标完。,2,3,4,5,1,2
13、,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,重复上述步骤，直至全部的点都标完。,2,3,4,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,重复上述步骤，直至全部的点都标完。,2,3,4,7,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,2,3,4,7,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,2,3,4,7,8,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,2,3,4,7,8,5,1,2,7,5,6,3,4,2,5,5,2,7,3
14、,1,3,5,7,1,0,2,3,4,7,8,13,5,1,2,7,5,6,3,4,2,5,5,2,7,3,1,3,5,7,1,0,2,3,4,7,8,13,小结,从点1出发，因L(1,1)=0，在点1处标记 从点1出发，找相邻点r使得边L(1,r)权数（距离）最小，若L(1,r) = L(1,1)+ d(1,r) 将 标于点r处。并将边1r变红。,0,L(1,r),从已标号的点出发，找与这些相邻点最小权数（距离）者，若L(1,p) =MinL(1,r)+ d(r,p) ，这里r为已标号者下标，p为未标号下标，则将 标于p处。并把(r,p)边变红。 重复上述步骤，直至全部的点都标完。,L(1,p),对有向图同样可以用标号算法： 例 如图，有一批货物要从v1运到v9，弧旁数字表示该段路长，求最短运输路线。,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,v1,v9,v8,v7,v6,v5,v4,v3,v2,3,3,3,3,3,4,2.5,5,2,2,2,1,4,0,3,v1,v9,v8,v7,v6,v
