基于城市道路网的快速路径寻优算法  

A Fast Algorithm for Optimum Path Based on a City Road Net

作　　者：毕军[1] 付梦印[1] 周培德[2] 张宇河[1] 

机构地区：[1]北京理工大学自动控制系 [2]北京理工大学计算机科学与工程系,北京100081

出　　处：《计算机工程》2002年第12期36-38,共3页Computer Engineering

摘　　要：从城市道路网的特点出发，描述了矢量化的城市道路网的存储结构，提出一种求解城市道路网两节点间最短路径的算法。算法基于双向式搜索原理，采用投影法、夹角最小的方法及二叉树理论。和Dijkstra算法相比，算法大大减小搜索空间，提高搜索速度，时间复杂性不超过O(N)，N为网络节点数。实际应用表明算法有很强的实用性和可靠性。According to the characteristics of a city road net, this paper discusses a kind of data structure of road net and proposes an algorithm for seeking the shortest path between two points in the road net. The algorithm takes advantage of the theories of bidirectional search, projection, minimum angle and binary tree. Compared with Dijkstra algorithm, the algorithm can reduce seeking space and can raise seeking speed greatly, and its time complexity can not exceed O(N), while N is the number of road net points. The application results show that the algorithm has good practicability and reliability.

关 键 词：城市道路网 快速路径寻优算法 路径规划 图论 二叉树理论 

分 类 号：U412.1[交通运输工程—道路与铁道工程] TP301[自动化与计算机技术—计算机系统结构]