一种基于边序列的任意两点间最短路径算法

被引：17

作者：

徐小玲

彭京

石葆梅

方全心

张竞

不详

机构：

[1] 成都天音数字有限公司

[2] 成都市公安局科技处

[3] 成都天音数字有限公司成都

[4] 成都

来源：

计算机工程与应用 | 2005年 / 29期

关键词：

边序列; 最短路径; Floyd; Dijkstra; 稀疏图;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

080201 [机械制造及其自动化];

摘要：

基于边序列信息,论文提出了一种新的求取任意两点间最短路径的算法:EBSP(EdgesBasedall-pairsShortestPathsAlgorithm)。该算法在算法时间复杂度上同Floyd算法相近,并在一定条件下相同;通过试验表明,在边数m满足m=c*n的情况下,EBSP算法速度约为Floyd算法的10倍到63倍。

引用

页码：88 / 90+103 +103

页数：4