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

Experimental Study of Heap Optimization of Dijkstra Shortest Path Algorithm

作　　者：张翰林[1] 关爱薇 傅珂[1] 孙廷凯[2] 

机构地区：[1]南京理工大学理学院,江苏南京210094 [2]南京理工大学计算机科学与工程学院,江苏南京210094

出　　处：《软件》2017年第5期15-21,共7页Software

基　　金：南京理工大学江苏省级大学生科研创新训练项目"Dijkstra最短路径算法的堆优化研究"

摘　　要：Dijkstra最短路径算法是图论的经典算法。设有向图G有n个顶点和m条弧,则该算法的时间复杂度为Θ(m+n^2)。前人的理论研究表明,若用二叉堆或d堆作为辅助数据结构,可不同程度地降低算法的时间复杂度。但是,这些研究给出的都是比较松弛的上界描述。本文设计了一系列实验,利用二叉堆和d堆实现了该算法的优化,并通过模型拟合回归的方式研究了优化算法的时间复杂度。我们发现,对于稠密图,采用二叉堆优化算法,实际的时间复杂度可降低为m和nlogn的线性函数;而采用d堆,时间复杂度可降低为m、ndlog_dn、nlog_dn、dlog_dn和n的线性函数,其中的d值对复杂度有显著影响,变化趋势呈现某些共同特征,而最优d值位于[5,7]区间。Dijkstra shortest path algorithm is a classical algorithm of graph theoty.Given graph G with n vert＆ and m arcs, the time complexity of this algorithm is 0（m ＋ n2） .The predecessors＇ theoretical research shows that if the binary heap or d-heap is used as the auxiliary data structure, the time complexity of the algorithm can be reduced to varying degrees.However, what these previous studies have given is relatively relaxed upper bounds.In this paper, we design a series of experiments,using binary heap and d-heap to realize the optimization of the algorithm, and through the method of model fitting and regression to study the time complexity of the optimized algorithms.We find that for the dense graph, using the binary heap, the actual time complexity can be reduced to the linear function of m and n log n ; and using the d-heap, the time complexity can be reduced to the linear function of m , nd logd n , nlogd n,d logd n and n . Moreover, the value of d has a significant impact on the complexity in terms of some common varying characteristics, and the optimal value of d is located at [5,7].

关 键 词：Dijkstra最短路径算法 二叉堆 d堆 时间复杂度 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]