常州大学学报（自然科学版）2011，Vol.23Issue(4)：45-49,5.
稀疏网络的一个最短路算法及其实现
A Shortest Path Algorithm for Large Sparse Network and Its Implement
李博 1李宁 2康慧燕 1元春梅1
作者信息
- 1. 常州大学数理学院,江苏 常州 213164
- 2. 常州大学信息科学与工程学院,江苏 常州 213164
- 折叠
摘要
Abstract
Shortest path algorithm has many important applications in transportation, communications, etc. Many problems arising from such networks may come down to a shortest path problems. On a network with nonnegative-length edges, Dijkstra's shortest path algorithm computes single-source shortest path in O (m + nlogn) time. The time bound assumes that a Fibonacci heap is used during the implementation of Dijkstra's algorithm. As the process of building heaps needs a little complex work, it makes the algorithm uneasy to be used. In this paper, we make use of the features of the large sparse network, make some very simple, but useful, changes in the original Dijkstra algorithm and obtain a new modified Dijkstra's shortest path algorithm for large sparse network. The new algorithm avoids the process of building heap and runs in O (m + nlog (n!)) time. Here m, n and D are the number of edges, vertices and the maximal number of edges incident with vertex, respectively. Thus, the new algorithm is very competitive for those sparse networks especially in road traffic networks in which D is often a small number.关键词
Dijkstra最短路算法/大型稀疏网络/Fibonacci堆Key words
Dijkstra's shortest path algorithm/large sparse network/Fibonacci heap分类
数理科学引用本文复制引用
李博,李宁,康慧燕,元春梅..稀疏网络的一个最短路算法及其实现[J].常州大学学报（自然科学版）,2011,23(4):45-49,5.
