关于改进GIS领域的最短路径Dijkstra算法研究

在GlS领域,对最短路径搜索问题的算法研究和应用属Dijkstra算法.但是,Dijkstra算法通常仅研究计算一条最短路径.文章通过对Dijkstra原始算法的基本原理和步骤进行分析研究,做如下改进:1、从已通过顶点集到未通过顶点集的可能存在的多条最短路径中,不丢弃任何一条最短路径.而Dijkstra原始算法仅在可能存在的多条最短路径中任选其中一条即可;2、Dijkstra算法的每一步骤,不仅要求路径最短,同时还要求经过的顶点最少,从而求出被原始算法忽略的所有可能存在的最短路径;结果最终可以求出带权图中一起始点到其余顶点的所有最段路径.

Improving Dijkstra Algorithm about the Shortest Path in GIS Field

There are many researches and applications about the shortest path searching in GIS field at present.But usually Dijkstra algorithm mainly is involved in studying the shortest path.The paper improves it in the following two aspects by analyzing and studying the basic principles and procedures of Dijkstra primary algorithm.The first is to choose any one of the impossible shortest path but it doesn't eliminate any of the impossible shortest path by passed top clusters to unpassed top cluster.The second is that in any procedure of Dijkstra algorithm it finds the shortest path and requires the least tops passed in order to get the impossible shortest path which is omitted by basic algorithm.As a result,the possible shortest path will be found with the weighted graphs from the starting point to the rest points.