【摘要】 在分析现有双向Dijkstra算法基础上,通过调整搜索规则,提出了一种改进的用中间链表加速的双向Dijkstra算法,保证了前向和后向搜索在中间相遇,大大地节省了算法的运行时间.经验证,算法的运行效率比传统Dijkstra算法平均提高90%.更多还原

【Abstract】 The shortest path dijkstra algorithm is one of the functions of spatial analyses, traditional Dijkstra algorithm, its time complex degree is as much as direct ratio to square of vertex number in graph, hard to meet practical count requirement under too many vertex condition. On the basis of analyzing current Bi-directional algorithm Dijkstra, this paper proposes an improved Bi-directional Dijkstra algorithm using intermediate list acceleration by adjusting seek strategy, to ensure forward and backward seek to meet in center, notably cutting down running time. To be tested, the running efficiency of this algorithm improves 90% on average than traditional Dijkstra algorithm.更多还原