基于MapX最短路径搜索算法研究

摘要

After the analysis of the shortest path search and special character, a new algorithm based on the MapX of part of the shortest path search is proposed, the algorithm search in a small rectangle based on the character that the shortest path is near the line which one point is the start point and the other is end point, it solved the fuzzy problem that made by surge, reduced the search the number of point and scale. A test showed that this algorithm run more fast, and more efficient in the complex road network, and it' s practicable.%在深入分析现有最短路径搜索算法和MapX空间特性的基础上,提出了一种基于MapX的局部最短路径搜索算法.该算法依据最短路径沿起点、终点连线方向可能性最大的特征,在小矩形范围内搜索,避免了因道路"振荡"而产生结果失真的问题,减少了搜索的节点数目,降低了搜索规模.实验结果表明,该算法搜索速度快,道路网络结构越复杂,其运行效率越高,具有很强的实用性.