[1]李博,李宁,康慧燕,等.稀疏网络的一个最短路算法及其实现[J].常州大学学报(自然科学版),2011,(04):45-49.
　LI Bo,LI Ning,KANG Hui-yan,et al.A Shortest Path Algorithm for Large Sparse Network and Its Implement[J].Journal of Changzhou University(Natural Science Edition),2011,(04):45-49.
点击复制

稀疏网络的一个最短路算法及其实现()
分享到：

常州大学学报(自然科学版)[ISSN:2095-0411/CN:32-1822/N]

卷:
期数:
2011年04期
页码:
45-49
栏目:
出版日期:
2011-09-30

文章信息/Info

Title:
A Shortest Path Algorithm for Large Sparse Network and Its Implement
作者:
李博1; 李宁2; 康慧燕1; 元春梅1
1常州大学 数理学院，江苏 常州 213164;2常州大学 信息科学与工程学院，江苏 常州 213164
Author(s):
LI Bo1; LI Ning2; KANG Hui-yan1; YUAN Chun-mei1
1School of Mathematics and Physics, Changzhou University, Changzhou 213164, China；2School of Information Science and Engineering, Changzhou University, Changzhou 213164, China
关键词:
Dijkstra最短路算法;  大型稀疏网络;  Fibonacci 堆
Keywords:
Dijkstra's shortest path algorithm;  large sparse network;  Fibonacci heap
分类号:
O 157.6
文献标志码:
A
摘要:
最短路算法在交通, 通信等领域有非常重要的应用, 许多网络问题都可以归结为一个最短路问题. Dijkstra最短路算法是一个非常有效的算法, 在计算网络中某一个顶点到其他各顶点的最短路时, 如果引入Fibonacci 堆, 则Dijkstra算法运行所需要的加法及比较次数大致为O(m+n.log n), 其中, m,n 分别为网络的边数和顶点数. 但由于在算法执行过程中, 对Fibonacci堆的操作也有一定的代价。 本文根据大型稀疏网络的特点, 对Dijkstra最短路算法提出了一些非常简单的, 但是非常有用的改进, 并由此得到一个针对大型稀疏网络的Dijkstra最短路算法, 该算法不需要构造Fibonacci堆, 并且算法在运行时也只需要加法与比较, 其所需要加法和比较的次数为O(m+n log (n!)), 其中D为网络中与顶点相关联边数的最大值. 对于大型稀疏网络, 如公路交通网络, D通常比较小, 因此, 所给算法对这类网络是非常有效的.
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+n log (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.

参考文献/References:

[1] Dijkstra E W. A note on two problems in connection with graphs［J］. Numer Math, 1959(1):269-271.
[2］Haldar S. An 'all pairs shortest paths' distributed algorithm using messages［J］. Journal of Algorithms, 1997,24:20-36.
[3］Fredman M L, Tarjan R E. Fibonacci Heaps and their uses in improved network optimization algorithm［J］. Journal of the ACM, 1987,34: 596-616.
[4］徐立华.求解最短路问题的一种计算机算法［J］. 系统工程, 1989,7(5):46-51.
[5］Saunders S, Takaoka T. Improved Shortest Path Algorithms for Nearly Acyclic Graphs［J］. Electronic Notes in Theoretical Computer Science, 2001,42:1-17.
[6］Xu M H, Liu Y Q, Huang Q L,et al. An improved Dijkstra’s shortest path algorithm for sparse network［J］. Applied Mathematics and Computation, 2007,185:247-254.
[7］Xu M H, William H K Lam, Shao H,et al. A heuristic algorithm for network equilibration［J］. Applied Mathematics and Computation, 2006,174:430-446.

备注/Memo

备注/Memo:
作者简介：李博（1978—），女，辽宁抚顺人，讲师。
更新日期/Last Update: 2011-09-30