首页 | 本学科首页   官方微博 | 高级检索  
     

交通道路网中任意两点之间最短路径的快速算法
引用本文:周培德. 交通道路网中任意两点之间最短路径的快速算法[J]. 计算机工程与科学, 2002, 24(4): 35-37
作者姓名:周培德
作者单位:北京理工大学计算机系,北京,100081
摘    要:寻找交通道路网中任意两点之间最短路径的算法已有许多 ,其中Dijkstra算法是最有效的算法之一 ,其时间复杂性为O(n2 )。本文提出的算法与Dijkstra算法不同 ,其主要思想是依据从始点至终点的直线段方向选择边产生二叉树 ,并采取有效方法降低二叉树的规模及缩短路径长度 ,然后由二叉树节点的标记计算出近似最短路径及其长度。反复执行常数次该算法可以求得最短路径及其长度。

关 键 词:最短路径  交通道路网  算法  复杂性
文章编号:1007-130X(2002)04-0035-03
修稿时间:2001-03-18

A Fast Algorithm for Finding the Shortest Path Between Arbitrary Two Points in a Traffic Road Net
ZHOU Pei de. A Fast Algorithm for Finding the Shortest Path Between Arbitrary Two Points in a Traffic Road Net[J]. Computer Engineering & Science, 2002, 24(4): 35-37
Authors:ZHOU Pei de
Abstract: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.
Keywords:shortest path  traffic road net  algorithm  complexity
本文献已被 CNKI 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号