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

摘要

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