城市复杂道路网的路线规划算法

迪杰斯特拉算法解决了图论中的最短路问题,但对于城市中包含禁左行、禁右行、立交桥等的复杂道路网的路线规划,该算法存在不足。文中给出复杂道路网的数据模型,在分析迪杰斯特拉最短路线搜索算法的基础上,针对城市道路的特征,提出一个改进的路线规划算法,该算法根据当前搜索顶点的入度数,对其进行多次标记,同时对进入该顶点的边进行标记。仿真试验的结果证明了该算法的正确性:在存在交通限制的情况下,也能规划出最优路线。

Route Planning Algorithm for Complicated Road Network in City

Dijkstra algorithm resolves shortest-path problem of graphs. But it exists shortage on route planning for real complicated road network which may be includes one-way street, cloverleaf junction and so on. A data model of complicated road network is introduced in this paper. Based on the analysis of Dijkstra algorithm,a modified route-planning algorithm is proposed according to the character of city road network. The algorithm makes more than one mark on vertex and simultaneously makes mark on edge which enters into the vertex. The best path can be planned on condition of cross limitation existing. Simulation and practice have prove the validity of this algorithm.