大规模网络最短路径算法的优化及实现  

Improvement and Realization of the Shortest Path Algorithm on the Large-scale Networks

作　　者：欧福军[1] 刘萍[2] 涂亚平 吴海兵[1] 

机构地区：[1]中国人民解放军炮兵学院研究生系,安徽合肥230031 [2]中国人民解放军炮兵学院军用网络工程教研室,安徽合肥230031

出　　处：《海南大学学报（自然科学版）》2008年第2期183-186,共4页Natural Science Journal of Hainan University

摘　　要：求解大规模复杂网络的最短路径问题由于其计算速度慢、需耗费的存储空间大,是与地理信息相关的应用系统经常遇到的瓶颈问题.在深入分析各种常用最短路径算法基础上,基于经典Dijkstra算法,从时间和空间优化角度,实现一种计算任意2点间最短路径的优化算法.初步实验表明,优化后的算法在处理大规模复杂网络的最短路径问题时比经典Dijkstra算法在计算时间上缩短了80%,在耗费的存储空间上减少了将近一倍.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.

关 键 词：最短路径算法 DIJKSTRA算法 算法效率 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]