Dijkstra最短路径算法的一种高效率实现

基金项目: 国家杰出青年科学基金和国家"九五"重点科技攻关资助项目,编号49525101 及96-B02-03

详细信息

An Efficient Implementation of Shortest Path Algorithm Based on Dijkstra Algorithm

National Laboratory for Information Engineering in Surveying, Mapping and Remote Sensing, WTUSM, 129 Luoyu Road, Wuhan, China, 430079

摘要: 在已存在的一些最短路径算法测试总结的基础上,根据GIS中网络计算的实际情况,从网络结构的拓扑表示以及Dijkstra算法中快速搜索技术的实现入手,提出了一种Dijkstra最短路径算法的高效率实现方法。
- 最短路径算法 /
- 网络分析 /
- 地理信息系统
Abstract: With the development of geographic information science and the wide use of GIS software, more and more needs are required to the network analyses. As the key of network analyses, computing the shortest paths over a network is an important problem that scholars facus on. Start with the data structure during its computation process and combined with F.Benjamin Zhan's evaluation of a set of 15 shortest path algorithms, this paper presents an efficient method of realize the shortest path algorithm which is based on Dijkstra algorithm. Result shows that this method performs well in practice.
- shortest path algorithm /
- network analysis /
- GIS