| 一种基于边序列的任意两点间最短路径算法 |
| |
| 引用本文： | 徐小玲,彭京,石葆梅,方全心,张竞. 一种基于边序列的任意两点间最短路径算法[J]. 计算机工程与应用, 2005, 41(29): 88-90,103 |
| |
| 作者姓名： | 徐小玲 彭京 石葆梅 方全心 张竞 |
| |
| 作者单位： | 成都天音数字有限公司,成都,610065;成都市公安局科技处,成都,610017 |
| |
| 摘 要： | 基于边序列信息,论文提出了一种新的求取任意两点间最短路径的算法:EBSP(EdgesBasedall-pairsShortestPathsAlgorithm)。该算法在算法时间复杂度上同Floyd算法相近,并在一定条件下相同;通过试验表明,在边数m满足m=c*n的情况下,EBSP算法速度约为Floyd算法的10倍到63倍。
|
| 关 键 词： | 边序列 最短路径 Floyd Dijkstra 稀疏图 |
| 文章编号： | 1002-8331-（2005）29-0088-03 |
| 收稿时间： | 2004-12-01 |
| 修稿时间： | 2004-12-01 |
A New All-pairs Shortest Paths Algorithm Based on Edge List |
| |
| Xu Xiaoling,Peng Jing,Shi Baomei,Fang Quanxin,Zhang Jing. A New All-pairs Shortest Paths Algorithm Based on Edge List[J]. Computer Engineering and Applications, 2005, 41(29): 88-90,103 |
| |
| Authors: | Xu Xiaoling Peng Jing Shi Baomei Fang Quanxin Zhang Jing |
| |
| Affiliation: | 1 Chengdu Tian-yin Digital Co. Ltd.,Chengdu 610065;2 Department of Science and Teehnology,Chengdu Public Security Bureau,Chengdu 610017 |
| |
| Abstract: | Based on the information of edge list in graph,this paper proposes a new all-pairs shortest path algorithm: EBSP (Edges Based All-pairs Shortest Paths Algorithm).The algorithm's complexity is similar to Floyd algorithm and the complexities of two algorithms are equal in some conditions.In experiment,we have proved that EBSP algorithm is 10 to 63 times faster than Floyd algorithm while the number of edges m is satisfied m=c*n. |
| |
| Keywords: | edge list shortest path Floyd Dijkstra sparse graph |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
