实际路网最短路径算法优化与实现

随着城市经济的飞速发展,汽车数量迅速增加,交通拥堵与污染问题不断加剧,为更好地解决此问题,智能交通系统研究应运而生。交通诱导系统是智能交通系统的重要子系统,一直以来就受到业界专家学者广泛深入的研究,而路径诱导系统中的关键点是最短路径算法,实际路网的单源最短路径算法中应用最广泛的是Dijkstra算法。由于Dijkstra算法的时间复杂度为2O(n),在解决两结点间的最短路径问题时,特别是对于大规模的城市道路网络,Dijkstra算法有很大冗余度。优化存储结构与搜索策略的最短路径算法成为降低算法存储空间、减少路径查询时间最为直接有效的方法。本文主要研究了Dijkstra算法在数据存储方面简单而必要的优化,重点对基于矩形搜索与双向搜索的实际路网最短路径优化算法进行研究并仿真验证,达到最大程度降低最短路径查询时间,降低最短路径算法冗余度和复杂度的目标。本文研究内容主要包括以下几个方面:(1)实际路网的数据预处理。主要工作内容是提出了路网经纬度数据处理方法,包括根据结点经纬度数据精确计算路段长度以及将结点经纬度数据转换成直角坐标表示的过程,并在此基础上对实际城市路网的特征进行了归纳总结。(2)基于限制搜索区域的最短路径算法研究。主要提出了基于矩形限制区域的Dijkstra算法,在数据预处理的基础上,给出了矩形算法的搜索面积范围与边界取值,并对此算法的有效性与可靠性进行理论分析与仿真验证。(3)基于双向搜索的最短路径算法研究。具体内容包括提出了双向搜索的终止条件,对终止条件的可靠性与有效性进行了理论证明,并在此基础上研究算法的搜索区域,对其改善程度进行仿真验证。