最短路径动态规划问题及其程序设计
林旭东
(深圳大学管理学院,广东深圳518060)
[摘要]本文以最短路径问题为例,在给出佛洛伊德算法的基础上,设计了求解该算法的计算程序,这样可大大提高最短路径计算的效率。

[关键词]最短路径; 动态规划; 程序设计
1 佛洛伊德算法
已知有n个顶点的有向图,佛洛伊德算法能够求解出每一对顶点之间的最短路径。

假设使用邻接矩阵d ( i, j)来对图进行存储, d ( i, j)表示υi 到υj 之间的距离,可是该距离不一定是最短距离。

佛洛伊德算法的基本思想是:为求顶点υi→υj 之间的最短距离,需要进行n次试探。

首先将υ0 加入路[收稿日期] - 12 - 22[作者简介]林旭东(1972 - ) ,男, 湖北武汉人,深圳大学管理学院副教授,博士后,主要研究方向:数量模型与决策分析。

径,考虑路径υi →υ0 →υj 是否存在,如果存在,则比较υi →υj和υi →υ0 →υj 的路径长度,取长度短的路径作为υi →υj 的路径,记作(υi ,υj ) 。

接着在路径上再增加一个顶点υ1 ,比较υi→υ1 →υj 和(υi ,υj )的路径长度, 取长度短的路径作为(υi ,υj) 。

不断将顶点υ2 ,υ3 , .,υn - 1加入进行试探, 最后得到的(υi ,υj )必定为υi →υj 的最短路径。

若使用数组dk ( i, j)表示加入顶点k后,最短路径长度的变化情况,使用数组pk ( i, j)表示加入顶点k后,最短路径上顶点的变化情况,这样佛洛伊德算法就会产生一组d 0 ( i, j) ,d1 ( i, j) , ., dn - 1 ( i, j)和一组p0 ( i, j) , p1 ( i, j) , ., pn - 1 ( i, j) 。

R2 =
01314 014 01286 0
01197 01263 01394 01146
01211 01281 01392 01116
01231 01308 01346 01115 ,
R3 =
01367 01409 01224 0
01402 01412 01186 0
01367 01409 01224 0
01326 01435 01239 0 。

(2) 利用层次分析法确定指标权重:A = (01123, 01769,01108) ,
A1 = (01201, 01206, 01324, 01269) , A2 = (01189,01323, 01195, 01293) , A3 = (01203, 01286, 01168, 01343) 。

(3) 对Vi和U作综合评价。

对Vi作综合评价,则有B1 =A1 ×R1 = (01356 8, 01380 3, 01222 2, 01040 6) , B2 = A2 ×R2= (01231 8, 01305 6, 01359 1, 01103 5) , B3 =A3 ×R3 = (01362 9,
01418 8, 01218 3)。

对U作综合评价,则有B = A ×R = A ×[B1 ,B2 , B3 ]T = (01261 3, 01327 0, 01327 1, 01084 6) 。

(4) 计算综合评价值:W = B ×CT = 21765,表明广西北部湾经济区物流竞争力相对比较强,这主要得益于该区域优越的物流竞争环境和强的竞争潜力。

因此, 广西北部湾经济区物流业有比较好的发展前景。

4 结束语
实践表明,灰色综合评价法应用于区域物流竞争力的综合评价是有效的、可靠的, 既能够评价一个区域物流竞争力所属的评价灰类,又能够对不同区域的物流竞争力进行选优排序,还能得出评价指标各组成要素的优劣排序, 所得评价信息可满足不同的评价需求。

然而,同其它定量分析方法一样,灰色综合评价法对区域物流竞争力的评价, 仍有一定的局限性和不确定性。

比如指标设置的代表性程度、专家评分以及指标权重的确定等都具有一定的主观性和随机性。

因此,在实际工作中应及时剔除突发因素的影响, 使模型评估结果更加符合实际。

主要参考文献
[ 1 ]姚建华. 物流产业竞争力评价指标体系研究[ J ]. 商业经济文荟, (1) : 20 - 23.
[ 2 ]李旭宏,李玉民,顾政华, 等. 基于层次分析法和熵权法的区域物流发展竞争态势分析[ J ]. 东南大学学报:自然科学版, , 34(3) : 398 - 401.
[3 ]谢如鹤,邱祝强,陈宝星. 区域物流产业竞争力指标体系及其应用
[ J ]. 工业工程, , 11 (1) : 109 - 112.
[ 4 ]邵万清. 物流产业评价指标与方法的探讨[ J ]. 物流科技, , 29(11) : 8 - 10.
[ 5 ]胡笙煌. 主观指标评价的多层次灰色评价法[ J ]. 系统工程理论与实践, 1996 (1) : 12 - 21.
[ 6 ]肖艳. 区域物流竞争力评价研究[D ]. 重庆:重庆大学机械工程学院, . [ 7 ]苏飞,唐万生. 商业银行授信风险分析的灰色综合评价法[ J ]. 哈尔滨理工大学学报, , 9 (4) : 47 - 51.
[ 8 ]邓聚龙. 灰色系统理论教程[M ]. 武汉: 华中理工大学出版社,1991: 144 - 162.84经济管理
最后dn - 1 ( i, j)和pn - 1 ( i, j)就是顶点υi 到υj 之间的最短距离和相应路径。

2 动态规划求解的佛洛伊德算法程序设计
如图1所示:给定一个线路网络,两点之间连线上的数字表示两点间的距离,求一条从A到E的路线,使总距离为最短。

下面设计的程序要求用邻接矩阵存储图1 上三角阵。

令υ1 ,υ2 , .,υ9 分别表示图1中点A, B1 , B2 , C1 , C2 , C3 , D1 ,D2 和E,则图1能够表示为(用99999表示∞) :
图1 动态规划的最短路径图
d ( i, j) =
99999 5 2 99999 99999 99999 99999 99999 99999
99999 99999 99999 3 7 99999 99999 99999 99999
99999 99999 99999 99999 6 3 99999 99999 99999
99999 99999 99999 99999 99999 99999 6 99999 99999
99999 99999 99999 99999 99999 99999 3 8 99999
99999 99999 99999 99999 99999 99999 99999 1 99999
99999 99999 99999 99999 99999 99999 99999 99999。