运筹学最短路径实验

1、实验项目：最短路径问题实验学时： 4实验日期： 2012 年 11 月 30 日 实验要求：案例 模型 分析 实验内容：用最短路径模型解决具体问题前言 运输是物流过程的主要职能之一，也是物流过程各项业务的中心活动。物流过程中 的其它各项活动， 如包装、装卸搬运、物流信息等， 都是围绕着运输而进行的。 可以说， 在科学技术不断进步、 生产的社会化和专业化程度不断提高的今天， 一切物质产品的生 产和消费都离不开运输。物流合理化，在很大程度上取决于运输合理化。所以，在物流 过程的各项业务活动中，运输是关键，起着举足轻重的作用。而有效的缩减路径可以使 得运输费用降低。本文运用 Dijkstra 算法求

2、出最短路径，以最大限度地节约运输费用降 低物流成本， Dijkstra 算法用于求解最短路径问题最常用的方法之一。Dijkstra 算法的基本步骤如下 ：（1）给起点v 1以P标号p v 1 0 ,其余各点均给以 T标号，TVi 。（2）若vi 点为刚得到的标号的点，考虑这样的点为 v j ，考虑 vi ,vj 这条边，且 vj 为T标号，对vj 的T标号进行如下更改T v jminT v j , Pv i l ij（3）比较所有具有标号的点，把最小者改为标号，即 PVimin vi ，当存在两个以上最小者时， 可同时改为标号， 若全部点均为标号， 则停止，否则v i 代v i 改为第二步重做

3、。案例分析下图所示是某地区交通运输的示意图，试问从 v1 出发，经哪条路线达到v8才能使总行程最短使用Dijkstra 求解。步骤：v81.首先给 v1以P标号， P V1 0 ,给其余所有的点以 T标号，T Vii 1,2,82.1）考察点 V1 ，边 V1,V2 , V1,V3T V2T V3min T V2 ,P V1 min T V3 ,PV1l12 minl13 min,0 4,0 62）比较所有 T 标号T V2 ,T V3 ，T V24 最小，所以给 V2以P 标号，PV2 4 ,记录路径 V1,V23. （1） V2 为刚得到 P标号的点，考察边V2,V4 , V2,V5T V

4、4min T V4 ,P V2l24 min,459T V5 min T V5 ,P V2l25 min,4482）比较所有 T 标号，T V3 ,T V4 ,T V5,T V3 6最小，给 V3以 P标号，P V3 6 ,记录路径 V1,V34. （1）V3 为刚得到 P标号的点，考察 V3,V4 , V3,V5T V4 min T V4 ,P V3l34min 9,6 4 9T V5min T V5 ,PV3l35min 8,6 7 82）比较所有 T 标号，TV4 ,TV5 ,TV5 8最小，给V5以 P标号，令P V5 8 ,记录路径 V2,V55. （1） V5为刚得到 P标号的点，

5、考察 V5,V6 , V5,V7T V6min T V6 ,P V5l56min,8 513T V7min T V7 ,P V5l57min,8 614（2）比较所有 T 标号， TV4 ,TV6,T V7 ,TV4 9最小,给V4以 P 标号,令 P V4 9 ，记录路径 V2,V46. （1）V4为刚得到 P标号的点，考察 V4,V6 , V4,V7T V6 min T V6 ,PV4 l46 min 13,9 9 13T V7 min T V7 ,P V4 l 47 min 14,9 7 14（2） 比较所有 T标号,T V6 ,T V7 ,T V6 13最小,给V6以P标号,令P V6

6、 13,记 录路径 V5,V67. （1） V6为刚得到 P标号的点，考察 V6,V7 , V6,V8T V7 min T V7 ,P V6 l67 min 14,13 4 14T V8 min T V8 ,P V6 l 68 min ,13 4 17（2）比较所有 T标号，T V7 ,TV8 ,T V7 14最小,给V7以P标号,令PV7 14, 记录路径 V5,V78. （1）V7 为刚得到 P标号的点，考察 V7,V8T V8 min T V8 ,PV7 l78 min 17,14 1 15（2）比较所有 T标号， T V8 15最小，给 V8以 P标号,令P V8 15 ,记录路 径 V7 ,V8至此可以得到最短路径为 V1 V2 V5 V7 V8 ,最短行程为 15实验总结科学合理的运输路线对物流的成本的大小影响很大。 Dijkstra 算法就是通过一种 方法，使运输路线最短，运费最少，尽可能的降低物流成本， 提高产品的竞争力， Dijkstra， 根据距 V1从近到远的顺序， 依次求得 V1到V