运筹学最短路径实验

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

2、，Dijkstra算法用于求解最短路径问题最常用的方法之一。Dijkstra算法的基本步骤如下：(1)给起点Vi以P标号pvi0,其余各点均给以T标号，TVi=。(2)若Vi点为刚得到的p标号的点，考虑这样的点为Vj,考虑Vi,Vj这条边，且Vj为T标号，对Vj的T标号进行如下更改TVjminTVj,PVilj(3)比较所有具有T标号的点，把最小者改为P标号，即PViminVi,当存在两个以上最小者时，可同时改为P标号，若全部点均为P标号，则停止，否则Vi代Vi改为第二步重做。案例分析下图所示是某地区交通运输的示意图，试问从V1出发，经哪条路线达到V8才能使总行程最短使用Dijkstra求解。

3、步骤:V81.首先给Vi以P标号，PVi0,给其余所有的点以T标号，TV1i1,2,82.(1)考察点Vi,边Vi,V2,Vi,V3TV2TV3minTV2,PV1minTV3,PV11213minmin,04,06(2)比较所有T标号TV2,TV3TV24最小，所以给V2以P标号,PV24,记录路径V1,V23.(1)V2为刚得到P标号的点，考察边V2,V4,V2,V5TV4minTV4,PV2l24min,4TV5minTV5,PV2l25min,4(2)比较所有T标号,TV3,TV4,TV5,TV36最小，给V3以P标号,PV36，记录路径Vi,V34.(1)V3为刚得到P标号的点,考察

4、V3,V4,V3,V5TV4minTV4,PV3134min9,649TV5minTV5,PV3l35min8,678(2)比较所有T标号,TV4,TV5,TV58最小，给V5以P标号，令PV58，记录路径V2V5. (1)V5为刚得到P标号的点,考察V5,V6,V5,V7TV6minTV6,PV5l56min,8513TV7minTV7,PV5I57min,8614(2)比较所有T标号，TV4,TV6,TV7,TV49最小，给V4以P标号，令PV49,记录路径V2,V46. (1)V4为刚得到P标号的点,考察V4,V6,V4,V7TV6minTV6,PV4l46min13,9913TV7mi

5、nTV7,PV4I47min14,9714(2)比较所有T标号，TV6,TV7,TV613最小，给V6以P标号，令PV613,记录路径V5,V67. (1)V6为刚得到P标号的点，考察V6,V7,V6,V8TV7minTV7,PV6l67min14,13414TV8minTV8,PV6&min,13417(2)比较所有T标号，TV7,TV8,TV714最小，给V7以P标号,令PV714,记录路径V5,V78. (1)V7为刚得到P标号的点，考察V7,V8TV8minTV8,PV7l78min17,14115(2)比较所有T标号，TV815最小，给V8以P标号，令PV815,记录路径V7,V8实验总结科学合理的运输路线对物流白成本的大小影响很大。Dijkstra算法就是通过一种方法，使运输路线最短，运费最少，尽可能的降低物流成本，提高产品的竞争力，Dijkstra,根据距V1从近到远的顺序，依次求得Vi到V8