资源描述：
《带有e约束的网络最短路算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第12卷第4期山东轻工业学院学报Vol.12No.41998年12月JOURNALOFSHANDONGINSTITUTEOFLIGHTINDUSTRYDec.1998带有e约束的网络最短路算法李汝修王薇察可文谢波(山东轻工业学院基础部济南250100)摘要网络最短路问题有一些成熟的算法,但对于带有约束条件的网络最短路问题这些算法却显得无能为力。本文将网络最短路问题的Dijkstra算法进行了推广,得到了带约束e的网络最短路算法,并将这一算法应用于解决实际问题,得到
2、了令人满意的结果。关键词约束,网络,最短路,Dijkstra算法中图法分类号O15751网络最短路问题的Dijkstra算法这种算法的基本原理是:若{V1,V2,,Vn-1,Vn}是V1Vn的最短路,则{V1,V2,,Vn-1}必是V1Vn-1的最短路。因为否则,若V1Vn-1的最短路是:{V1,Vi,Vi,23Vi,Vn1}。那么V1Vn的最短路就是:{V1,Vi2,Vi3,Vi,Vn1,Vn},与设矛盾!n-2n-2若以Lij表示从Vi到Vj的最短距离,则Dijkstra
3、算法的步骤如下:(1)对起点进行标号,每个标号点的标号包含两部分:前者表明它的标号是从哪点而来的,后者表示从起点到该点的总距离,所以从Vs出发,将Lss=0填进Vs旁边的圆括号内,表示Vs点已标号;(2)从Vs出发,找出与Vs相邻顶点Vr中Wsr最小的一个,将Lsr=Wsr的值填进Vr旁的圆括号内,表明Vr也已标号;(3)从已标号顶点出发,找出与这些Vr顶点紧邻的所有顶点,若:Lsp=min(Lsr+Wrp),则对Vp标号,将Lsp的值填进Vp旁的圆括号内。r(4)重复(3)直到所有的顶点都标号
4、为止。圆括号内的数字,即为从Vs点到该点的最短距离。因第一个标号指明所沿的路径,运用反追踪法可找出这条路径。针对具体问题将上述过程用计算机语言编程就可得到求解过程。2推广的Dijkstra算法对于下面的网络问题,要求从VsVt的最短路。假若各边的权重已经给定,且其后续路径不同时其权重带有不同的约束e;即如下图(1)所示,当沿路径VsV1到达顶点V1后,其后续路径有三条,沿不同的路径寻找最短路时,该边的实际权重应等于该边的权重加上因其后续路径不同而带有的不同的约束条件e;这时前面的Dijkstr
5、a算法无法解决这样的问题。我们收稿日期:1997-11-24第4期李汝修等:带有e约束的网络最短路算法73将Dijkstra算法进行下面的推广。如图所示,设边VsV1的权重为已知,设为E(s,1),边V1V4的权重为E(1,4),边V1V6的权重为E(1,6),边V1V3的权重为E(1,3),而沿边VsV1到V1后,其后续路径分别为V1V4,V1V6,V1V3时,其约束分别为e(1,4),e(1,6),e(1,3),这时我们采取如下的处理方法:要求VsVT的最短路径,我们采用一种预测的方法,因
6、为边VsV1的权重已表示出,为E(s,1),其后续路径有三条,每条路径对应的约束为e(1,4),e(1,6),e(1,3),则从VsV1出来后沿不同路径的实际权重为E(s,1)+e(1,4),E(s,1)+e(1,6),E(s,1)+e(1,3);同理,若边V1V3图1网络图a的实际权重为已知,则从该边到VT的路径有两条,它们分别经过V3V5,V3V6,这两条边的权重分别为E(3,5)和E(3,6),其约束设为e(3,5)和e(3,6),按照上述方法,沿这两条不同路径前进时,该两边的实际权重应
7、为E(3,5)+e(3,5)和E(3,6)+e(3,6)这样在标号的过程中,我们对于每一边的实际权重都要按照其后续路径的多少而标记数个不同的实际权重值。采用上述处理方法,按照一般网络问题的Dijkstra算法的标号方法,就可以得到VsVT的最短路径。这就是推广的Dijkstra算法。将这一算法编程实现,就可以利用它来解决一类相当广泛的实际问题。3推广的Dijkstra算法的应用某些工业部门常用截断切割的加工方式从一长方体中加工出一个已知尺寸,位置预定的长方体(这两个长方体的对应面是平行的
8、),通常要经过六次截断切割。设水平切割单位面积的费用是垂直切割单位面积费用的r倍,且当先后两次垂直切割的平面(不管他们之间是否穿插水平切割)不平行的,因调整刀具需额外费用e。要求设计一种加工切割次序,使总费用最省。31问题的简化首先可以证明,沿同一方向的切割可以选择切割顺序时,应先切掉体积最大的一块(证明从略)。因此在进行切割时,对各平行面的第一次切割只有一种选择。我们把对各面切割的加工顺序画成下面的网络图(图2):图中大长方体中每一个小长方体的每一条边都表示一种截断切割加工工序,如VsV1
