| 城市道路最短路径的Dijkstra算法优化 |
| |
| 引用本文： | 张渭军,王华.城市道路最短路径的Dijkstra算法优化[J].长安大学学报(自然科学版),2005,25(6):62-65. |
| |
| 作者姓名： | 张渭军 王华 |
| |
| 作者单位： | 1. 长安大学,地球科学与国土资源学院,陕西,西安,710054
2. 陕西交通职业技术学院,经济管理系,陕西,西安,710021 |
| |
| 基金项目： | 国家自然科学基金项目（60072044） |
| |
| 摘 要： | 在研究城市道路网络特征基础上,建立城市道路网络模型及其数据库,应用一种改进的Dijkstra算法对城市道路进行最短路径查询,该算法是从起点和终点分别用二叉树按起点到终点和终点到起点的方向进行搜索.在计算某一段最短路径时,用Dijkstra算法时间为0.23 s,改进算法时间为0.20 s.仿真结果表明,该算法不仅在时间上有所改进,其时间复杂度由传统Dijkstra算法的O（n^2）减小为O（n）,而且其所选的最优路径更符合实际,是一种寻求最优路径的有效算法.
|
| 关 键 词： | 交通工程 道路网络 数据库 Dijkstra算法 最短路径 二叉树 |
| 文章编号： | 1671-8879（2005）06-0062-04 |
| 收稿时间： | 2004-11-09 |
| 修稿时间： | 2004年11月9日 |
Optimination Dijkstra arithmetic for shortest path of urban traffic net |
| |
| ZHANG Wei-jun,WANG Hua.Optimination Dijkstra arithmetic for shortest path of urban traffic net[J].JOurnal of Chang’an University:Natural Science Edition,2005,25(6):62-65. |
| |
| Authors: | ZHANG Wei-jun WANG Hua |
| |
| Abstract: | This paper established the road net model and database of urban traffic based on the study of the urban traffic road character.The shortest path was queried by the improving Dijkstra arithmetic,the arithmetic used B-tree in the start and end point separately in the direction of start-end and end-start.The times are 0.20 s and 0.23 s when using Optimination Dijkstra arithmetic and the Dijkstra arithmetic.The simulation results indicate that the complex grade in time is minished to O(n) from the Dijkstra's O(n~2),the shortest path is agreed with the practice,the(arithmetic) is an effective method in selecting the shortest path.2 tabs,1 fig,7 refs. |
| |
| Keywords: | traffic engineering road net datebase Dijkstra arithmetic shortes path B-tree |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
