计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2005年
29期
88-90,103
,共4页
徐小玲%彭京%石葆梅%方全心%张竞
徐小玲%彭京%石葆梅%方全心%張競
서소령%팽경%석보매%방전심%장경
边序列%最短路径%Floyd%Dijkstra%稀疏图
邊序列%最短路徑%Floyd%Dijkstra%稀疏圖
변서렬%최단로경%Floyd%Dijkstra%희소도
基于边序列信息,论文提出了一种新的求取任意两点间最短路径的算法:EBSP(Edges Based all-pair Shortest Paths Algorithm).该算法在算法时间复杂度上同Floyd算法相近,并在一定条件下相同;通过试验表明,在边数m满足m=c*n的情况下,EBSP算法速度约为Floyd算法的10倍到63倍.
基于邊序列信息,論文提齣瞭一種新的求取任意兩點間最短路徑的算法:EBSP(Edges Based all-pair Shortest Paths Algorithm).該算法在算法時間複雜度上同Floyd算法相近,併在一定條件下相同;通過試驗錶明,在邊數m滿足m=c*n的情況下,EBSP算法速度約為Floyd算法的10倍到63倍.
기우변서렬신식,논문제출료일충신적구취임의량점간최단로경적산법:EBSP(Edges Based all-pair Shortest Paths Algorithm).해산법재산법시간복잡도상동Floyd산법상근,병재일정조건하상동;통과시험표명,재변수m만족m=c*n적정황하,EBSP산법속도약위Floyd산법적10배도63배.