一类标准矩形网络节点间最短路径的求解方法

A kind of solving method for the shortest path between standard rectangular network nodes

针对常见的交通道路最短路径问题,提出标准矩形网络的概念,分析其节点间最短路径的性质,并在此基础上给出一种新颖的最短路径求解算法.该算法利用标准矩形网络的几何性质,简化了搜索方向和步长的判断,同时指出常见的交通道路网络一般均可以整体或部分化为标准矩形网络.与常见的求取最短路径的Dijkstra、Floyd、ACO、A*等算法进行仿真实验比较,实验结果表明,对于大规模标准矩形道路网络,所提出算法具有更好的寻优精度、稳定性和寻优速度.

In view of the shortest path problem of the common traffic road, the standard rectangular network concept is proposed, the properties of the shortest path between nodes are analyzed, and a novel shortest path algorithm based on the standard rectangular network（SRNSP） is presented. By using the geometric properties of the standard rectangular network,the search direction and step judgment are simplified. Meanwhile, it is pointed out that some or even all of the common traffic road networks can be converted into standard rectangular networks. Compared with the common Dijkstra, Floyd,ACO and A＊ algorithms for solving the shortest path problem, the experiment results show that the proposed algorithm has better optimization accuracy, stability and searching speed for the large-scale standard rectangular road network.