基于GIS的最短路径算法研究

摘要

针对单源最短路径Dijkstra算法效率低的问题,基于地理信息系统(GIS:Geographic Information System),提出距离均衡的社区分析网络分割方法。将GIS中道路网络分割降解为距离均衡的社区网络,再利用限制分层算法,通过淘汰不太可能出现在最短路径上的节点,限制GIS中最短路径的搜索区域,以降低算法的复杂度。实验结果表明,优化后的算法可有效减少搜索节点数,与经典算法相比,其运行效率有所提高。