在深入分析传统Dijkstra算法的基础上，提出了利用基于ｋ叉堆的优先级队列对算法进行改进的思想，并对3种可合并替进行了比较，从理论上证明了四叉堆在ｋ叉堆中的最优性，设计了基于四叉堆优先级队列及逆领接表，顾及路段方向阻抗的改进型Dijkstra最短径算法，将Dijkstra算法复杂度降为O(nlogn)。

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 amongk-ary heap. The presented algorithm decreases the complexity of conventional Dijkstra algorithm toO(logn). 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.