改进型Dijkstra算法在GIS中的应用  

An Improved Algorithm of Dijkstra in GIS Field

作　　者：赵娜[1] 

机构地区：[1]太原师范学院,太原030012

出　　处：《电脑开发与应用》2012年第3期74-75,78,共3页Computer Development & Applications

基　　金：省级软件科学基金资助项目(2007041011-02)

摘　　要：使用Dijkstra算法搜索最短路径是地理信息系统的应用研究的一个重要组成部分。Dijkstra算法无法找到所有的最短路径,所提到的改进型算法是结合了Dijkstra算法和一定的数据结构,使得某个路径顶点到其他目标顶点的所有最短路径可以非常便捷地被找到,而且这种改进型的算法并没有增加原有算法的复杂性,故有较好的研究和实用价值。It is an important part of the application of GIS of using the Dijkstra algorithm to search shortest path problem.The Dijkstra algorithm can not find all the shortest paths.An improved algorithm is presented in this article,which combines Dijkstra algorithm with some data structure and all shortest path from one vertex to other vertex can be be found easily.And this improved algorithm did not increase the complexity of the original algorithm,so it has good research and practical value.

关 键 词：DIJKSTRA算法 最短路径 GIS 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]