稀疏网络的一个最短路算法及其实现

• 作者: 元春梅 康慧燕 李博 李宁
• 来源期刊: 常州大学学报(自然科学版)
• 学科: 数学
• 关键词: Dijkstra最短路算法 大型稀疏网络 Fibonacci堆
• 年，卷（期）: 2011,（4）
• 所属期刊栏目: 信息与计算机技术
• 页码范围: 45-49
• 分类号: O157.6
• 字数: 3572字
• 语种: 中文
• DOI: 10.3969/j.issn.2095-0411.2011.04.011

摘要

最短路算法在交通,通信等领域有非常重要的应用,许多网络问题都可以归结为一个最短路问题.Dijkstra最短路算法是一个非常有效的算法,在计算网络中某一个顶点到其他各顶点的最短路时,如果引入Fibonacci堆,则Dijkstra算法运行所需要的加法及比较次数大致为O (m+nlogn),其中,m,n分别为网络的边数和顶点数.但由于在算法执行过程中,对Fibonacci堆的操作也有一定的代价.本文根据大型稀疏网络的特点,对Dijkstra最短路算法提出了一些非常简单的,但是非常有用的改进,并由此得到一个针对大型稀疏网络的Dijkstra最短路算法,该算法不需要构造Fibonacci堆,并且算法在运行时也只需要加法与比较,其所需要加法和比较的次数为O (m+nlog(n!)),其中D为网络中与顶点相关联边数的最大值.对于大型稀疏网络,如公路交通网络,D通常比较小,因此,所给算法对这类网络是非常有效的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李宁	常州大学信息科学与工程学院	30	57	5.0	6.0
2	元春梅	常州大学数理学院	4	11	2.0	3.0
3	李博	常州大学数理学院	4	9	2.0	3.0
4	康慧燕	常州大学数理学院	3	2	1.0	1.0