《运筹学最短路径实验》由会员分享，可在线阅读，更多相关《运筹学最短路径实验（4页珍藏版）》请在金锄头文库上搜索。
1、实验项目:最短路径问题实验学时:4实验日期:2012年11月30日实验要求:案例模型分析实验内容:用最短路径模型解决具体问题刖言运输就是物流过程的主要职能之一，也就是物流过程各项业务的中心活动。物流过 程中的其它各项活动，如包装、装卸搬运、物流信息等都就是围绕着运输而进行的。可 以说,在科学技术不断进步、生产的社会化与专业化程度不断提高的今天,一切物质产品 的生产与消费都离不开运输。物流合理化,在很大程度上取决于运输合理化。所以，在物 流过程的各项业务活动中，运输就是关键,起着举足轻重的作用。而有效的缩减路径可以 使得运输费用降低。本文运用Dijkstra算法求出最短路径，以最大限度地节约运输
2、费用 降低物流成本,Dijkstra算法用于求解最短路径问题最常用的方法之一。Dijkstra算法的基本步骤如下：(1) 给起点v以P标号pV)二0 ,其余各点均给以T标号,T V.L +。11i(2) 若v点为刚得到的p标号的点，考虑这样的点为v，考虑V ,v )这条边，且i ji j(.)为T标号，对v的T标号进行如下更改 jj)= minTC )P()+ l jjiij(3) 比较所有具有T标号的点，把最小者改为P标号，即pV )= mini. 当存在两ii个以上最小者时，可同时改为P标号，若全部点均为P标号，则停止，否则匸代v改为第ii二步重做。案例分析下图所示就是某地区交通运输的示意
3、图，试问从v出发，经哪条路线达到v才能使1 8总行程最短？使用Dijkstra求解。95v5V8V3V17步骤：1.首先给V以P标号，P（V ）= 0，给其余所有的点以T标号，T（V）=+/二1,2,A ,8）1 1i2.（1）考察点 V，边（V ,V ）,（V, V ）11213T（V ）= min It（V ） P（V ）+1 二 minT（V ）= minT V） pQ）+ 厂 二 min C-,0 + 6= 63 3113（2）比较所有T标号（V ）T（V ）, T（y ）= 4最小，所以给V以P标号，令2 322P（V ）= 4，记录路径（V,V ）2 1 23、（1） V为刚得到P
4、标号的点,考察边（V ,V ）,（V ,V ）2 2425T（V ）= min f （V ） P （V ）+ 1 = min La, 4 +94 4224T（V ）= min T（V ） P（V ）+ 1 = min La, 4 +85 5225（2）比较所有T标号，（V ）, T（V ）, T（V ）, T（V ）= 6最小，给V以P标号，令3 4533P（V ）= 6，记录路径（V, V ）3 134、（1） V为刚得到P标号的点，考察（V ,V ）（V ,V ）3 3435T（V ）= min T（V ） P（V ）+1 =min b,6+94 4334T（V ）= min=min k,
5、6 +85 5335（2）比较所有T标号，（V ）, T（V ）, T（V ）= 8最小，给V以P标号，令4 555P(V )= 8,记录路径(V ,V )5 255、(1) V为刚得到P标号的点，考察(V ,V ),(V , V )5 5657T(V )= min T(V )P(V )+1 L min L8 + 5= 136 6556T(V )= min It(V ) p (y)+ 1 L min La, 8 + 6= 147 7557(2)比较所有T标号，&(V )T(V )T(V ), T/)= 9最小，给V以P标号，令4 6744P(V )= 9，记录路径(V , V )4246、(1
6、) V为刚得到P标号的点，考察(V ,V ),(V ,V )44647T (V )= min tr (v ), p (v )+1 =min 13,9 +136 6446T (V )= min T (V ) P (V )+1 =min 14,9 + 7 L147 7447(2)比较所有T标号，r(V ), T(V ), T(V )= 13最小，给V以P标号，令P(V )= 13,6 7666记录路径(V ,V )5 67、(1) V为刚得到P标号的点，考察(V ,V )(V ,V )6 6768T(V )= min T(V ) P(V )+1 二 min 14,13 +147 7667T(V )
7、= min T(V ) P(V )+1 L min La,13 + 4= 178 8668(2)比较所有T标号，&(V ),T(V ), T(V )= 14最小，给V以P标号，令7 877P(V )= 14 ,记录路径(V , V )7578、(1) V为刚得到P标号的点，考察(V ,V )778T(V )= min 卜(V ) P(V )+1 二 min 17,14 + 1L158 8778(2)比较所有T标号，T(V )= 15最小，给V以P标号，令P(V )= 15，记录路径8 8 8(V ,V )78至此可以得到最短路径为V T V T V T V T V ,最短行程为1512578实验总结科学合理的运输路线对物流的成本的大小影响很大。Dijkstra算法就就是通过 一种方法，使运输路线最短，运费最少，尽可能的降低物流成本，提高产品的竞争 力,Dijkstra,根据距V从近到远的顺序，依次求得V到V各顶点的最短路径与距离,直1 1 8至V ,算法结束。根据记录的最后路径（V ,V ）逆推至（V ,V ）,（V ,V ）,（V,V ），总结出路径8 78572512为V V V V V ,所以最短距离为15、12578
