关键词: 交通运输系统工程, 交通诱导, 最短路径, 路网表达, 数据结构

Abstract: 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 connectivity of the road network, eliminate its node weights, reduce the time complication degree and the search space, enhance the search efficiency of the shortest path algorithm due to the introduction of two pointerarrags which make the node locating fast and accurate.

Key words: engineering of communications and transportation system, traffic guidance, shortest path, representation of road network, data structure