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

• 作者: 周培德
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 最短路径 交通道路网 算法 复杂性
• 年，卷（期）: 2002,（4）
• 所属期刊栏目: 算法研究
• 页码范围: 35-37
• 页数: 3页
• 分类号: TP301.6
• 字数: 2900字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2002.04.011

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周培德	北京理工大学计算机系	28	414	12.0	20.0