%0 Journal Article
%T Improved Dijkstra Algorithm Based on Quad Heap Priority Queue and Inverse Adjacent List<br>基于四叉堆优先级队列及逆邻接表的改进型Dijkstra 算法
%A Lu Feng
%A Lu Dongmei
%A Cui Weihong
%A <br>陆锋
%A 卢冬梅
%A 崔伟宏
%J 中国图象图形学报
%D 1999
%I 
%X 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.
%K Shortest path algorithm
%K Quad
%K heap
%K Priority queue
%K Geographic Information Systems<br>最短路径算法
%K 四叉堆
%K 优先级队列
%K 地理信息系统
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=D06194629680C940ACE75262F54B9D85&aid=80662A1E44125396F7446D119D413109&yid=B914830F5B1D1078&vid=E158A972A605785F&iid=59906B3B2830C2C5&journal_id=1006-8961&journal_name=中国图象图形学报&referenced_num=16&reference_num=0