当前位置:
文档之家› 运筹学最短路径实验word精品
运筹学最短路径实验word精品
实验项目:最短路径问题
实验学时:4
实验日期:2012年11月30日
实验要求:案例模型分析
实验内容:用最短路径模型解决具体问题
刖言
运输是物流过程的主要职能之一,也是物流过程各项业务的中心活动。物流过程中 的其它各项活动,如包装、装卸搬运、物流信息等,都是围绕着运输而进行的。可以说, 在科学技术不断进步、生产的社会化和专业化程度不断提高的今天,一切物质产品的生 产和消费都离不开运输。物流合理化,在很大程度上取决于运输合理化。所以,在物流 过程的各项业务活动中,运输是关键,起着举足轻重的作用。而有效的缩减路径可以使 得运输费用降低。本文运用Dijkstra算法求出最短路径,以最大限度地节约运输费用 降低物流成本,Dijkstra算法用于求解最短路径问题最常用的方法之一。
(2)比较所有T标号,「TV7,T V8 ?,T V7=14最小,给V7以P标号,令
7为刚得到P标号的点,考察V7,V8
T V8=minTy,PV7I7J = min 17,14 1〕=15
(2)比较所有T标号,T V8=15最小,给V8以P标号,令PV8=15,记录路 径V7,V8
(2)比较所有T标号,汀V4,T V6,TV I,T V4=9最小,给V以P标号,令PV4]=9,记录路径V2,V4
6.(1)V4为刚得到P标号的点,考察V4,V6,V4,V7
T V6二minTV6FV4 J =min 13,9 +9】=13 T V7二mi nTV7,PV4n 14,9 7 L14
T VU-minT V5,PV2I25=min〔::,4 4=8
(2)比较所有T标号,^TV3,TV4,TV5\ T V3=6最小,给V以P标号,令
PV3=6,记录路径V1,V3
4.(1)V3为刚得到P标号的点,考察V3,V4,V3,V5
T V4二mi nTV4,PV3l3J-mi n9,64〕=9
至此可以得到最短路径为—V2rV5rV7rV8,最短行程为15
实验总结
科学合理的运输路线对物流的成本的大小影响很大。Dijkstra算法就是通过一
种方法,使运输路线最短,运费最少,尽可能的降低物流成本,提高产品的竞争力,Dijkstra,根据距V从近到远的顺序,依次求得V1到V各顶点的最短路径和距离,直至V8,算法结束。根据记录的最后路径逆推至V5,V7,V2,V5,VV,总结出路
(2)比较所有T标号,汀V6,T V7 1,T V6=13最小,给V以P标号,令PV6=13,记录路径V5,V6
7.(1)V为刚得到P标号的点,考察V6,V7,V6,V8
T V7=min T V7,P V6 I6J=min 14,13 41 = 14 T Vs二min T V8, P V6b丄min〔,13 4丨-17
Dijkstra
(1)给起点V!以P标号PV!二0,其余各点均给以T标号,TV=o
(2)若Vi点为刚得到的P标号的点,考虑这样的点为Vj,考虑Vi,Vj这条边,且Vj为T标号,对Vj的T标号进行如下更改
TVj二minTvj,PViI」
(3)比较所有具有T标号的点,把最小者改为P标号,即PV二mi门匕】,当存 在两个以上最小者时,可同时改为P标号,若全部点均为P标号,则停止,否则v:代Vi改为第二步重做。
T V5二mi nTV5,PV3l3J-mi n 8,67 I-8
(2)比较所有T标号,<TV4,T V5 \T V5 =8最小,给V以P标号,令
PV5=8,记录路径V2M
5.(1)V为刚得到P标号的点,考察WWW
T V6]=minT V6,P乂l5J- min〔::,8 51-13
T%i=minT V7,P V5I57=minI::,8 6=14
径为Vi>V2>V5>V7,所以最短距离为15.
T V3=minTV3,Pyl1J-min〔::,06丨-6
(2)比较所有T标号^T V2,T V3\,TV^-4最小,所以给V2以P标号,令
PV2=4,记录路径V1,V2
3.(1)V2为刚得到P标号的点,考察边V2,V4,V2,V5
T V4i;=min T V4,P V2l2J- mi n〔::,45丨-9
案例分析
下图所示是某地区交通运输的示意图,试问从v1出发,经哪条路线达到v8才能使总
行程最短?使用Dijkstra求解。
步骤:
1.首先给vi以P标号,PVi=0,给其余所有的点以T标号,T乂i=1,2,…,8
2.(1)考察点Vi,边MN,Vi,V3
TV2AminTv2,P« l12=min〔::,04=4