| 大规模网络最短路径算法的优化及实现 |
| |
| 引用本文： | 欧福军,刘萍,涂亚平,吴海兵. 大规模网络最短路径算法的优化及实现[J]. 海南大学学报(自然科学版), 2008, 26(2): 183-186 |
| |
| 作者姓名： | 欧福军 刘萍 涂亚平 吴海兵 |
| |
| 作者单位： | 中国人民解放军炮兵学院研究生系,安徽合肥,230031;中国人民解放军炮兵学院军用网络工程教研室,安徽合肥,230031 |
| |
| 摘 要： | 求解大规模复杂网络的最短路径问题由于其计算速度慢、需耗费的存储空间大，是与地理信息相关的应用系统经常遇到的瓶颈问题．在深入分析各种常用最短路径算法基础上，基于经典Dijkstra算法，从时间和空间优化角度，实现一种计算任意2点间最短路径的优化算法．初步实验表明，优化后的算法在处理大规模复杂网络的最短路径问题时比经典Dijkstra算法在计算时间上缩短了80％，在耗费的存储空间上减少了将近一倍．
|
| 关 键 词： | 最短路径算法 Dijkstra算法 算法效率 |
Improvement and Realization of the Shortest Path Algorithm on the Large-scale Networks |
| |
| OU Fu-jun,LIU Ping,TU Ya-ping,WU Hai-bing. Improvement and Realization of the Shortest Path Algorithm on the Large-scale Networks[J]. Natural Science Journal of Hainan University, 2008, 26(2): 183-186 |
| |
| Authors: | OU Fu-jun LIU Ping TU Ya-ping WU Hai-bing |
| |
| Affiliation: | OU Fu-jun LIU Ping ,TU Ya-ping ,WU Hai-bing ( 1. The Department of Graduate-study, Artillery College of PLA, Hefei 230031, China; 2. The Research Group of Network Engineering for Army Application, Artillery College of PLA,Hefei 230031, China) |
| |
| Abstract: | To solve the shortest path problem on large-scale complicated networks is very difficult because it will use a mass of time and storage space. It is related to application systems about geographic information systems. After analyzed a lot of shortest path problem common algorithms and based the classic Dijkstra algorithm, a kind of algorithm to calculate the shortest path in discretional two spot was realized. The experiment has indicated that the optimized algorithm has shortened 80% on calculation time and decreased one order of magnitude on used space by comparing with the classic Dijkstra algorithm. |
| |
| Keywords: | the shortest path algorithm Dijkstra algorithm algorithm efficiency |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
