| 空间分析中双向Dijkstra算法优化研究 |
| |
| 引用本文： | 张奋,黄铁,周军辉.空间分析中双向Dijkstra算法优化研究[J].湖南文理学院学报(自然科学版),2007,19(2):71-73,86. |
| |
| 作者姓名： | 张奋 黄铁 周军辉 |
| |
| 作者单位： | 湖南文理学院计算机基础部 湖南常德415000(张奋)，湖南文理学院计算机科学系 湖南常德415000(黄铁)，湖南民族职业学院网络中心 湖南岳阳414000(周军辉) |
| |
| 基金项目： | 湖南省教育厅科研项目(05C719) |
| |
| 摘 要： | 在分析现有双向Dijkstra算法基础上,通过调整搜索规则,提出了一种改进的用中间链表加速的双向Dijkstra算法,保证了前向和后向搜索在中间相遇,大大地节省了算法的运行时间.经验证,算法的运行效率比传统Dijkstra算法平均提高90%.
|
| 关 键 词： | 空间分析 最短路径 中间链表 双向Dijkstra算法 优化 |
| 文章编号： | 1672-6146（2007）02-0071-03 |
| 修稿时间： | 2007-04-08 |
Optimization Research for Bi-directional Dijkstra Algorithm of Spatial Analyses |
| |
| ZHANG Fen,HUANG Tie,ZHOU Jun-hui.Optimization Research for Bi-directional Dijkstra Algorithm of Spatial Analyses[J].Journal of Hunan University of Arts and Science:Natural Science Edition,2007,19(2):71-73,86. |
| |
| Authors: | ZHANG Fen HUANG Tie ZHOU Jun-hui |
| |
| Institution: | 1. Department of Basic Computer, Hunan University Of Arts and Science, Changde Hunan 415000; 2. Department of Computer, Hunan University Of Arts and Science, Changde Hunan 415000; 3. Network Center, Hunan National Vocational College, Yueyang Hunan 414000 |
| |
| 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. |
| |
| Keywords: | spatial analyses the shortest path intermediate list the bi-directional Dijkstra algorithm optimization |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
