空间分析中双向Dijkstra算法优化研究  

Optimization Research for Bi-directional Dijkstra Algorithm of Spatial Analyses

作　　者：张奋[1] 黄铁[2] 周军辉[3] 

机构地区：[1]湖南文理学院计算机基础部,湖南常德415000 [2]湖南文理学院计算机科学系,湖南常德415000 [3]湖南民族职业学院网络中心,湖南岳阳414000

出　　处：《湖南文理学院学报（自然科学版）》2007年第2期71-73,86,共4页Journal of Hunan University of Arts and Science(Science and Technology)

基　　金：湖南省教育厅科研项目(05C719)

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

关 键 词：空间分析 最短路径 中间链表 双向Dijkstra算法 优化 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]