一种改进的最短路径搜索算法

AN IMPROVED SHORTEST PATH SEARCH ALGORITHM

在深入分析现有最短路径搜索算法和MapX空间特性的基础上，提出了一种基于MapX改进的局部最短路径搜索算法。该算法依据最短路径沿起点、终点连线方向可能性最大的特征，在小矩形范围内搜索，避免了因道路“振荡”而产生结果失真的问题，减少了搜索的节点数目，降低了搜索规模。实验结果表明，该算法搜索速度快，道路网络结构越复杂，其运行效率越高，具有很强的实用性。

After thoroughly analysing the shortest path search algorithm and the spatial character of MapX, a MapX-based improved local shortest path search algorithm is proposed; it searches within a small rectangular scope according to the characteristic that the shortest path is most possible along the direction of the line connecting start point and end point, so that it is free from the result distortion problem caused by road ＂oscillation＂, reduces the number of nodes searched and the search scope. Test result shows that the algorithm has a faster search speed. The more complicated the road network is, the more efficient it operates ; it has very strong practicability as well.