交通网络限制搜索区域时间最短路径算法

在基于四叉堆优先级队列的改进型Ｄｉｊｋｓｔｒａ 最短路径算法的基础上，进一步提出了利用交通网络的空间分布及方位特征构造限制区域的时间最短路径算法。在对城市交通网络空间分布特征进行统计分析的基础上，针对具体的起、终节点，设定合理的椭圆限制搜索区域，以减少算法的搜索规模。针对椭圆限制搜索区域算法由于计算量大而效率不高的弱点，提出了矩形限制搜索区域算法，达到既减小算法搜索规模，又提高算法运行效率的目的。试验结果显示了本文提出的限制搜索区域算法的合理性与有效性

Time Shortest Path Algorithm for Restricted Searching Area in Transportation Networks

Transportation networks have apparent characteristics of spatial distribution, which is the basic difference between the sparse graphs describing the transportation networks and other planar graphs describing topological structure or hierarchical structure. A time shortest path algorithm based on the restricted searching area is presented in this paper. On the basis of quadary priority queue and inverse adjacent list data structure, a restricted searching area algorithm is established, based on the statistical analysis on the spatial distribution of transportation networks, with the appropriate restricted ellipse and rectangle areas for appointed start and destination nodes. The restricted rectangle searching area is proved more appropriate as the restricted area. Considering the different road travelling impedance and turn impedance, a time shortest path algorithm is presented. The presented algorithms can efficiently decrease the searching scale and improve the running efficiency. It has been proved by some tests on the real world transportation network.