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

摘要：

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

关键词：边序列、最短路径、Floyd、Dijkstra、稀疏图

所属期刊栏目：41

分类号：TP311(计算技术、计算机技术)

在线出版日期：2005-11-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：88-90,103