Dijkstra最短路径算法的堆优化实验研究

• 作者: 傅珂 关爱薇 孙廷凯 张翰林
• 来源期刊: 软件
• 学科: 工学
• 关键词: Dijkstra最短路径算法 二叉堆 d堆 时间复杂度
• 年，卷（期）: 2017,（5）
• 所属期刊栏目: 基金项目论文
• 页码范围: 15-21
• 页数: 7页
• 分类号: TP301.5
• 字数: 7246字
• 语种: 中文
• DOI: 10.3969/j.issn.1003-6970.2017.05.004

摘要

Dijkstra最短路径算法是图论的经典算法.设有向图G有n个顶点和m条弧,则该算法的时间复杂度为2(Θm+n).前人的理论研究表明,若用二叉堆或d堆作为辅助数据结构,可不同程度地降低算法的时间复杂度.但是,这些研究给出的都是比较松弛的上界描述.本文设计了一系列实验,利用二叉堆和d堆实现了该算法的优化,并通过模型拟合回归的方式研究了优化算法的时间复杂度.我们发现,对于稠密图,采用二叉堆优化算法,实际的时间复杂度可降低为m和nlogn的线性函数;而采用d堆,时间复杂度可降低为m、ndlogd n、nlogd n、dlogd n和n的线性函数,其中的d值对复杂度有显著影响,变化趋势呈现某些共同特征,而最优d值位于[5,7]区间.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	孙廷凯	南京理工大学计算机科学与工程学院	9	76	4.0	8.0
2	张翰林	南京理工大学理学院	1	9	1.0	1.0
3	关爱薇	南京理工大学理学院	1	9	1.0	1.0
4	傅珂	南京理工大学理学院	1	9	1.0	1.0