最短路径搜索算法的几种优化改进

介绍了GIS领域最短路径搜索的一种优化模式.在Dijkstra's算法的基础上,从三个方面改进了最短路径的计算.首先引入了多级路线图,在读取线路数据时,根据路线的级别有所选择;其次,在计算最短距离时考虑速度的影响;最后,在道路的转弯处,引入虚拟路径来估算转弯对汽车行驶的影响.应用以上三种方法的实验,取得了很好的效果.

SEVERAL OPTIMIZATION FOR THE SHORTEST PATH SEARCH ALGORTHM

An optimized pattern for the shortest path computation in GIS is presented.Based on Dijkstra's shortest path algorithm,the shortest path computation is optimized in three aspects.Firstly,a graph-subgraph structural hierarchy is imposed on an input data set.Secondly,speed effect is taken into consideration in the shortest path computation.Finally,a pseudo path is added to reckon the turning point.The experiment utilizing these three optimization means has achieved satisfactory results.