求解最短路问题的一种优化矩阵算法

被引:19
作者
林华珍
周根贵
机构
[1] 浙江工业大学经贸管理学院
关键词
最短路问题; 矩阵算法; 优化;
D O I
10.16772/j.cnki.1673-1409.2007.04.006
中图分类号
O224 [最优化的数学理论];
学科分类号
070105 [运筹学与控制论];
摘要
矩阵算法是求解不含负回路的网络中所有顶点对之间最短路的有效算法之一,但当节点比较多时,计算的矩阵多,重复计算量大,降低了计算效率。为此,提出了一种优化的矩阵算法,该算法的思路是利用权矩阵计算网络任意两节点之间的最短路长。计算实例表明,优化的矩阵算法减少了重复计算,简化了路径标注方法,提高了计算效率。
引用
收藏
页码:14 / 16+172 +172-173
页数:5
相关论文
共 6 条
[1]
运筹学教程.[M].胡运权主编;.清华大学出版社.2003,
[2]
网络算法与复杂性理论.[M].谢政;李建平 编写.国防科技大学出版社.1995,
[3]
运筹学.[M].钱颂迪主编;.清华大学出版社.1990,
[4]
运筹学.[M].翁龙年;亢耀先 编.人民邮电出版社.1988,
[5]
[6]
无向网络中最短路径的标记与减少计算量的方法 [J].
任平安 ;
李文莉 .
纺织高校基础科学学报, 2001, (01) :48-50