Improved Dijkstra Algorithm Based on Quad Heap Priority Queue and Inverse Adjacent List
基于四叉堆优先级队列及逆邻接表的改进型Dijkstra 算法

An improved Dijkstra algorithm is set forward on the basis of priority queue based on quad heap. It is proved in this paper that quad heap is the optimum among k ary heap. The presented algorithm decreases the complexity of conventional Dijkstra algorithm to O (log n ). Considering the dynamic characters of transportation applications, an inverse running sequence is presented based on the inverse adjacent list data structure. It is more suitable for the dynamic applications of GIS T.