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

被引：38

作者：

周培德

机构：

[1] 北京理工大学计算机系北京

来源：

计算机工程与科学 | 2002年 / 04期

关键词：

最短路径; 交通道路网; 算法; 复杂性;

D O I：

暂无

中图分类号：

U491 [交通工程与交通管理];

学科分类号：

摘要：

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

引用

页码：35 / 37

页数：3