%0 Journal Article
%T The Calculation of the Shortest Path Using Modified Dijkstra Algorithm in GIS<br>GIS中使用改进的Dijkstra算法 实现最短路径的计算
%A TANG Wen-wu
%A SHI Xiao-dong
%A ZHU Da-kui
%A <br>唐文武
%A 施晓东
%A 朱大奎
%J 中国图象图形学报
%D 2000
%I 
%X In GIS it is necessary to optimize the analysis function of the shortest path as the hinge of spatial network analysis, which includes shortest path analysis, resource allocation and isochrone, and so on. Here derived from the traditional calculating method, i.e. Dijkstra algorithm, the analysis procedure of the shortest path is improved by adopting the data structure of binary heap to complete the operation of priority queue. Initialization, Extraction, and Relzxztion. The topological structure of geographical network data and the detailed implementing steps of the shortest path are also discussed. Furthermore, the visualizing calculation of the shortest path is completed by COM(Component Object Model) techniques, and the calculating procedure is encapsulated into the component of the geographic network class. The complexity analysis and the case of this algorithm showes that the modified algorithm is applicable to improve the efficiency of spatial analysis of the net system.
%K Dijkstra algorithm
%K Priority queue
%K Binary hT<br>Dijkstra算法
%K 二叉堆
%K 网络分析
%K GIS
%K 最短路径计算
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=D06194629680C940ACE75262F54B9D85&aid=6208AC676C9C3412&yid=9806D0D4EAA9BED3&vid=94C357A881DFC066&iid=59906B3B2830C2C5&sid=CBC69BEA05C12902&eid=A40901B6135B333E&journal_id=1006-8961&journal_name=中国图象图形学报&referenced_num=35&reference_num=8