摘要
用Dijkstra算法求解大规模网络两顶点间最短路径时,需计算大量与最短路径无关的顶点,效率较低.双向定界搜索算法是首先对网络进行双向搜索,得到一条经任意点的最短路径.一般情况下,这条路径已非常接近、甚至等于最短路径.然后,以此路径的标号(即路径长)作为搜索计算的界,进行双向标号计算,对超过界的顶点不再计算,以提高计算效率.算法分析表明,用该算法可使计算效率提高约一倍.
Many irrelevant vertexes must be searched in order to find the shortest path between two vertexes in a large network with Dijkstra algorithm, resulting in low efficiency. To improve the searching efficiency, a new searching algorithm, named bidirectional bound searching algorithm, was proposed. With this method, a shortest path from the source vertex to the terminal vertex via any vertex is determined first by bidirectional searching. This path is closed to or even is same as the shortest path to be found. The length of this path is then taken as a bound, and any vertex with larger label value than the bound in later calculations will not be considered. It was proved that the calculating efficiency of the new algorithm was as twice as that of the traditional Dijkstra algorithm.
出处
《西南交通大学学报》
EI
CSCD
北大核心
2004年第5期561-564,共4页
Journal of Southwest Jiaotong University
基金
国家自然科学基金资助项目(70071028)
关键词
网络分析
最短路径
双向定界搜索算法
效率
network analysis
shortest path
bidirectional bound search algorithm
efficiency