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

摘要

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