一种面向城市复杂路网最短路径提取的定向收敛算法

摘要

为提高城市复杂路网最短路径提取的效率,针对路网数据量大、结构密集等特点,研究了路网节点之间最短路径的分布特征,通过引入收敛点方式,设计并实现了一种面向复杂路网最短路径快速提取的定向收敛算法.为检验该算法的有效性,利用某城市道路交通网络进行了实验和分析,并与Dijsktra算法、A*算法等比较,证实了该算法能够提高路径搜索效率,且随着城市路网规模的扩大定向收敛算法的高效性将愈加明显.%For the purpose of enhancing the efficiency of the shortest path extraction based complex urban road network, considering the characteristics of large data and complex layout in urban road network, this paper studied the distribution of the shortest path between nodes, and proposed orientation convergent algorithm towards the rapid extraction of the shortest path in urban road network concerning the convergent node.The experiments validates the algorithm through a city' s traffic networks.In comparison with the existing algorithm, i.e.Dijkstra algorithm, the A* algorithm and so on, this method proves to be more effective.The testing results that the high efficiency of orientation convergent algorithm is more obvious with the expansion of the scale of urban road network.