运筹学最短路邮递员问题

最短路问题最短路问题是最重要的优化问题之一，它不仅可以直接应用于解决生产实际的许多问题例如各种管道的铺设、线路的安排、厂区的布局、设备的更新等等，而且经常被作为一个基本工具，用于解决其它优化问题如运输网络的最小费用流等。（最短距离、费时最少、费用最省）定义（权、赋权图）：对图G的每一条边e，可赋与一个实数w（e）称为边e的权。图G连同它边上的权称为赋权图。路中边权最小的称为最短路。权可以表示铁路长度，通讯网络的造价，网络中表示耗时等。狄克斯拉（Dijkstra）算法•最短路问题可以化为线性规划问题求解，也可以用动态规划方法求解，这里介绍一种有效算法—狄克斯拉（Dijkstra）算法，这一算法是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）=p（vi）+ωij，则记k（vj）=vi（前点标记）;•3°找出具有最小T标号的点，将其标号改为p标号。若vt已获得p标号，则已找到最短路，由k（vt）反向追踪，就可找出vs到vt的最短路径，p（vt）就是vs到vt的最短距离。否则，转2°。例求图中v1到v8的最短路。v4v23265v3v5v6v7v863552111479解：标p（v1）=0，其余点标T（vi）=+∞，i=2,3,4,5,6,7,8;T（v2）=min{+∞,0+3}=3,k（v2）=v1T（v3）=min{+∞,0+5}=5,k（v3）=v1T（v4）=min{+∞,0+6}=6,k（v2）=v1将具有最小T标号的v2点的标号改为p标号：p（v2）=3；T（v3）=min{5,3+1}=4,k（v3）=v2T（v5）=min{+∞,3+7}=10,k（v5）=v2T（v6）=min{+∞,3+4}=7,k（v6）=v2目前，点v3具有最小T标号，将其标号改为p标号：p（v3）=4；v1v4v23265v3v5v6v7v8635211149v17p（v1）=0p（v2）=3p（v3）=4T（v4）=min{6,4+1}=5,k（v4）=v3T（v6）=min{7,4+2}=6,k（v6）=v3目前，点v4具有最小T标号，将其标号改为p标号：p（v4）=5；T（v6）=min{6,5+3}=6;T（v7）=min{+∞,5+5}=10,k（v7）=v4目前，点v6具有最小T标号，将其标号改为p标号：p（v6）=6；T（v5）=min{10,6+2}=8,k（v5）=v6T（v7）=min{10,6+1}=7,k（v7）=v6T（v8）=min{+∞,6+9}=15,k（v8）=v65目前，点v7具有最小T标号，将其标号改为p标号：p（v7）=7；T（v8）=min{15,7+5}=12,k（v8）=v7;p（v5）=8；T（v8）=min{12,8+6}=12,p（v8）=12；反向追踪找最短路径。最短路径为：v1→v2→v3→v6→v7→v8；因p（v8）=12，所以v1→v8的最短距离为12。最短路问题不仅可以求解交通图中两点之间的最短距离，实际中很多问题也可变为最短路问题加以求解。例如设备更新问题，厂区合理布局问题等。兹举一例：例1（设备更新问题）某企业使用一台设备，在每年年底，企业都要决策下年度是购买一台新设备呢？还是继续使用这台设备。若购买新的，就要支付一笔购置费；如果使用旧设备，只要支付维修费，而维修费随着设备的使用年限延长而增加。现根据以往统计资料已经估算出设备在各年初的价格和不同使用年限的修理费用，分别如表1、表2所示。试确定一个五年内的设备更新计划，使五年内总支出最小。图上标示法下面我们结合例3介绍求解最短路问题的图上标示法，它比狄克斯拉算法更简洁。年份一二三四五购置费1111121213表1使用年限0~11~22~33~44~5年修理费5681118表2解：先根据表1、表2的数据画出设备更新费用网络图，如下图所示。图中点vi表示第i年开始，弧（vi,vj）表示设备第i年初使用到第j年初，弧（vi,vj）上的权数表示该期间设备所需的费用。这样，求五年内设备最优更新方案便转化为求v1→v6的最短路。v1v2v3v4v5v6161617171822304159223041233123设d（vi）表示点vi到终点的最短距离，根据动态规划最优性原理，最短路径中任何子路径也必然是最短的。因此有d（vi）=min｛ωij+d（vj）｝注意，上式要对以vi为起点的所有弧（vi,vj）进行计算。然后将计j算结果直接标在图中点vi的旁边，同时标出与点vi最近的邻接点。先从点v5算起，逆向进行。v1v2v3v4v5v61616171718223041592230232341对于点v5：d（v5）=18，v5→v6；18v5→v6对于点v4：d（v4）=min｛17+18,23｝=23，v4→v6；23v4→v6对于点v3：d（v3）=min｛17+23,23+18,31｝=31，v3→v6；3131v3→v6对于点v2：d（v2）=min｛16+31,22+23,30+18,41｝=41，v2→v6；41v2→v6对于点v1：d（v1）=min｛16+41,22+31,30+23,41+18,59｝=53,v1→v3；或v1→v4。53v1→v3→v6或v1→v4→v6109631702115132861722291511914397463109631702115132861722291511914397463从一点到任意点的最短路•木器厂有六个车间，办事员经常要到各个车间了解生产进度。从办公室到各车间的路线由图1给出。找出点1（办公室）到其它各点（车间）的最短路5127563425527313571距离、价格123252边eij或记为（vi，vj）点（vi）权wij(dij)表示网络图形的特点•1、与欧氏几何的区别为，图中线的长短并不能表示真实的长度。•2、与地图的区别为两点之间的距离并不真实。表示网络图形的特点•网络（图论）中两点之间的距离由两点间的边上的权来表示。（可由图中的点1、2与点1、3之间的关系来看）。求网络上的一点到其它点的最短路Dijkstra算法图示Dinkstra标号法•这是解决网络中某一点到其它点的最短路问题时目前认为的最好方法。•在这个问题中我们讨论的是从网络中的点1到其它各点的最短路。51275634255273135710①从点1出发，因L11=0，在点1处标记5127563425527313571051275634255273135710从已标号的点出发，找与这些相邻点最小权数（距离）者，找到之后：标号；边变红。51275634255273135710251275634255273135710③从已标号的点出发，找与这些相邻点最小权数（距离）者，找到之后：标号；边变红。251275634255273135710③从已标号的点出发，找与这些相邻点最小权数（距离）者，找到之后：标号；边变红。2351275634255273135710④重复上述步骤，直至全部的点都标完。2351275634255273135710④重复上述步骤，直至全部的点都标完。23451275634255273135710④重复上述步骤，直至全部的点都标完。23451275634255273135710④重复上述步骤，直至全部的点都标完。234751275634255273135710234751275634255273135710234785127563425527313571023478512756342552731357102347813512756342552731357102347813小结•①从点1出发，因L(1,1)=0，在点1处标记•②从点1出发，找相邻点r使得边L(1,r)权数（距离）最小，若L(1,r)=L(1,1)+d(1,r)将标于点r处。并将边1r变红。0L(1,r)•③从已标号的点出发，找与这些相邻点最小权数（距离）者，若L(1,p)=Min{L(1,r)+d(r,p)}，这里r为已标号者下标，p为未标号下标，则将标于p处。并把(r,p)边变红。•④重复上述步骤，直至全部的点都标完。L(1,p)对有向图同样可以用标号算法：例如图，有一批货物要从v1运到v9，弧旁数字表示该段路长，求最短运输路线。v1v9v8v7v6v5v4v3v23333342.55222140v1v9v8v7v6v5v4v3v23333342.552221403v1v9v8v7v6v5v4v3v23333342.552221403v1v9v8v7v6v5v4v3v23333342.5522214034v1v9v8v7v6v5v4v3v23333342.5522214034v1v9v8v7v6v5v4v3v23333342.55222140345v1v9v8v7v6v5v4v3v23333342.55222140345v1v9v8v7v6v5v4v3v23333342.5522214034665v1v9v8v7v6v5v4v3v23333342.5522214034665v1v9v8v7v6v5v4v3v23333342.55222140346756v1v9v8v7v6v5v4v3v23333342.552221403467568.5v1v9v8v7v6v5v4v3v23333342.552221403467568.59v1v9v8v7v6v5v4v3v23333342.552221403467568.59最短路的矩阵算法首先写出弧长矩阵D第一步：划去矩阵D中第一列，并给第一行以标号0。第二步：在已标号中未划去的元素中，寻找出最小的元素aij并圈起来，此时把第j列划去，同时给第j行标号i。并把第j行中未划去的各元素都加上aij。第三步：如果各行均已获得标号，则停止，并利用标号倒向追踪，得到v1到各点的最短路。若存在未标号行，返回第二步。例求v1到各点vj的最短路。v1v4v2v5v3v61253242324412v1v2v3v4v5v6v1012v2034v32051v4404v5230v6220v1v2v3v4v5v60012v2034v32051v4404v5230v6220v1v2v3v4v5v60012v2034v32051v4404v5230v6220v1v2v3v4v5v60012v2034v32051v4404v5230v6220v1v2v3v4v5v60012103+14+1v32051v4404v5230v6220v1v2v3v4v5v600121045v32051v4404v5230v6220v1v2v3v4v5v600121045v32051v4404v5230v6220v1v2v3v4v5v600121045v320511404v5230v6220v1v2v3v4v5v600121045v320511404+2v5230v6220v1v2v3v4v5v600121045v320511406v5230v6220v1v2