交通道路网中任意两点之间最短路径的快速算法

A Fast Algorithm for Finding the Shortest Path Between Arbitrary Two Points in a Traffic Road Net

寻找交通道路网中任意两点之间最短路径的算法已有许多 ,其中Dijkstra算法是最有效的算法之一 ,其时间复杂性为O(n2 )。本文提出的算法与Dijkstra算法不同 ,其主要思想是依据从始点至终点的直线段方向选择边产生二叉树 ,并采取有效方法降低二叉树的规模及缩短路径长度 ,然后由二叉树节点的标记计算出近似最短路径及其长度。反复执行常数次该算法可以求得最短路径及其长度。

There have been many algorithms for finding the shortest path between arbitrary two points in a traffic road net. Among these the Dijkstra's algorithm is one of the most effective algorithms, its time complexity is O( n 2 ). The algorithm presented in this paper is different from Dijkstra's. Its main idea is that we select edges and build a binary tree according to the direction of a straight line segment from the start point to the finish point, and adopt an effective method to reduce the size of the binary tree and shorten the length of the path, then calculate the approximate shortest path and its length in terms of the labels of the binary tree's nodes. Repeatedly implementing this algorithm a constant times can obtain the shortest path and the length.