交通诱导系统中道路网络的表达与存储方法

考虑实际道路网络的特殊性以及最短路径算法对路网信息的要求,运用对偶图法的基本思想对前向关联边结构进行了改进,提出了一种能够提高路径优化算法实时性的路网表达方法与数据存储结构,并用Dijkstra和A*最短路径算法进行了验证。结果表明,这种方法在清楚表达转向限制、消除结点权重的同时,由于两个指针数组的引入,使得算法可以迅速而准确地定位相关结点的位置,从而减小了搜索空间,降低了最短路径算法的时间复杂度,提高了最短路径的搜索效率。

Representation and storage method for road network of traffic guidance system

Considering the particularity of the road network and the demand of the shortest path algorithm for the road network information,a new method of representation and storage of the road network to enhance the real-timeness of the shortest path algorithm was proposed based on the basic idea of the dual graph representation to improve the forward star structure.The method was tested against the classic shortest path algorithms such as Dijktra and A*.The results show that the method can clearly express the conne...