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

• 作者: 张竞 彭京 徐小玲 方全心 石葆梅
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 边序列 最短路径 Floyd Dijkstra 稀疏图
• 年，卷（期）: 2005,（29）
• 所属期刊栏目: 学术探讨
• 页码范围: 88-90,103
• 页数: 4页
• 分类号: TP311
• 字数: 3852字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2005.29.026

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	彭京	成都市公安局科技处	9	429	8.0	9.0
2	石葆梅	成都市公安局科技处	2	58	2.0	2.0
3	徐小玲		1	19	1.0	1.0
4	方全心	成都市公安局科技处	1	19	1.0	1.0
5	张竞		1	19	1.0	1.0