运筹学最短路径实验_第1页
运筹学最短路径实验_第2页
运筹学最短路径实验_第3页
运筹学最短路径实验_第4页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

运筹学最短路径实验实验项目:最短路径问题实验学时:4实验日期:20121130实验要求案例模型分析实验内容:用最短路径模型解决具体问题前言运输就是物流过程的主要职能之一,也就是物流过程各项业务的中心活动。物流过DijkstraDijkstra算法的基本步骤如下:给起点

Pp1

0TTV1

。若vi

点为刚得到的ｐ标号的点,考虑这样的点为vj

,vi j

这条边,且v Tvj

的T标号进行如下更改Tj

minTvj

i

lij(3)比较所有具有Ｔ标号的点,把最小者改为Ｐ标号,即P

i

,当存在两个以上最小者时,可同时改为Ｐ标号,若全部点均为Ｐ标号,则停止,否则vvi

改为第二步重做。0运筹学最短路径实验运筹学最短路径实验PAGEPAGE1案例分析v1

出发,经哪条路线达到v8

才能使总行程最短？使用Dijkstra求解。v 5 v 9 v2 4 64 4 7 5 4v v1 86 4 5 1v3步骤:

7 v 6 v5 7首先给v1

P1

0TTi

i1,2,,8(1)考察点

,边

,V,V1 1 2 1 3T

min,0442

2

12 TV minTV3

,PV l1

,066(2)比较所有T2

3

T2

4最小,所以给V2

以P标号,令PV2

4,记录路径,V1 23、 (1)V2

P,V2 4

,V2 5Tl ,4594 4 2 24TV5

5

2

l25

min,448(2)比较所有T3

4

5

T3

6最小,给V3

以P标号,令PV3

6,记录路径,V1 34、 (1)V3

P,V3 4

,V3 5T4T

4

3

l34l

49min8,6785 5 3 35(2T4

5

T5

8最小,给V5

以P标号,令PV5

8,记录路径,V2 55、(1)V5

P,V5 6

,V5 7T6T

6

5

l56l

,8513,86147 7 5 57(2)比较所有T标号4

6

7

T4

9最小,给V4

以P标号,令9,记录路径,V4 2 46、(1)V4

P,V4 6

,V4 7T6T7

67

44

l46l47

913714(2)比较所有T6

7

T6

13最小,给V6

以P6

13,记录路径,V5 67、(1)V6

P,V6 7

,V6 8T7T

7

6

l67l

min14,13414min,134178 8 6 68(2)比较所有T标号,7

8

T7

14V7

以P标号,令PV7

14,记录路径,V5 78、(1)V7

P,V7 8TV8

8

7

l78

min17,14115,V7 8

(2)比较所有TT8

15最小,给V8

以P8

15,记录路径至此可以得到最短路径为VV1 2

VV5

V158实验总结科学合理的运输路线对物流的成本的大小影响很大。Dijkstra力,Dijkstra,根据距V1

从近到远的顺序,依次求

人人文库> 全部分类> 行业资料 > 管理策划

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论