实验项目：最短路径问题

实验学时： 4

实验日期：2012年11月30日

实验要求：案例 模型 分析

实验内容：用最短路径模型解决具体问题

前言

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

Dijkstra算法的基本步骤如下：

（1）给起点以P标号,其余各点均给以T标号， 。

（2）若点为刚得到的ｐ标号的点，考虑这样的点为，考虑这条边，且为T标号，对的T标号进行如下更改

（3）比较所有具有Ｔ标号的点，把最小者改为Ｐ标号，即，当存在两个以上最小者时，可同时改为Ｐ标号，若全部点均为Ｐ标号，则停止，否则代改为第二步重做。

案例分析

下图所示是某地区交通运输的示意图，试问从出发，经哪条路线达到才能使总行程最短使用Dijkstra求解。

5 9

4 4 7 5 4

6 4 5 1

7 6

步骤：

1.首先给以P标号，,给其余所有的点以T标号，

2.（1）考察点，边

（2)比较所有T标号，最小，所以给以P标号，令,记录路径

3. (1) 为刚得到P标号的点，考察边

（2）比较所有T标号，,最小，给以P标号，令,记录路径

4. （1）为刚得到P标号的点，考察

（2）比较所有T标号，,最小，给以P标号，令

,记录路径

5. （1) 为刚得到P标号的点，考察

（2）比较所有T标号，,最小,给以P标号,令，记录路径

6. （1）为刚得到P标号的点，考察

(2) 比较所有T标号,,最小,给以P标号,令,记录路径

7. （1）为刚得到P标号的点，考察

(2)比较所有T标号，,最小,给以P标号,令,记录路径

8. （1）为刚得到P标号的点，考察

（2）比较所有T标号，最小，给以P标号,令,记录路径

至此可以得到最短路径为,最短行程为15

实验总结

科学合理的运输路线对物流的成本的大小影响很大。Dijkstra算法就是通过一种方法，使运输路线最短，运费最少，尽可能的降低物流成本，提高产品的竞争力，Dijkstra，根据距从近到远的顺序，依次求得到各顶点的最短路径和距离，直至，算法结束。根据记录的最后路径逆推至，，，总结出路径为，所以最短距离为15.