OALib Journal期刊
GIS领域最短路径搜索问题的一种高效实现
DOI: 10.11834/jig.200308343
Keywords: 地理信息系统(420？3040) ,Dijkstra ,最短路径
Abstract:
目前在GIS领域，对最短路径搜索问题的研究和应用较多，其中最短路径搜索算法的效率问题是普遍关注和在实际应用中迫切需要解决的问题.通过对基于Dijkstra最短路径搜索算法的优化途径的分析，从算法本身和数据存储结构两个方面同时对此问题的解决方案进行了优化，提出了直线优化Dijkstra算法，并进行了必要的证明和适用条件论述.此方案应用到“全国主要城市间公路信息查询”系统中，取得了较为满意的效果，同时也给出了相关的测试数据
References
[1] ［1］徐业昌,李树祥,朱建民等.基于地理信息系统的最短路径搜索算法[J].中国图象图形学报,1998,3(1):39～43. [2] 严寒冰,刘迎春.基于GIS城市道路网最短路径算法探讨[J].计算机学报,2000,23(2):210-215. [3] ［5］Cherkassky B V, Goldberg A V, Radzikt. Shortest paths algorithms: Theory and experimental evaluation [ J ].Mathematical Programming, 1996,73:129～ 174. [4] ［7］Zhan F B, Noon C E. Shortest path algorithms:An evaluation [J]. Using Real Road Networks[J]. Transportation Science,1998,32(1):65～73. [5] ［9］方世昌.离散数学[M].西安:西安电子科技大学出版社,1995:254～256. [6] ［2］陆锋.最短路径算法:分类体系与研究进展[J].测绘学报,2001,30(3):269～275. [7] ［4］吴京,景宁,陈宏盛.最佳路径的层次编码及查询算法[J].计算机学报,2000,23(2):184～189. [8] ［6］Bertsekas D P. A simple and fast label correcting algorithm for shortest paths [J]. Networks, 1993,23: 703 ～ 709. [9] ［8］严蔚敏,吴伟民.数据结构(第2版)[M].北京:清华大学出版社,1997:159～281.
Full-Text
Contact Us
service@oalib.com
QQ:3279437679
WhatsApp +8615387084133
