城市道路最短路径的Dijkstra算法优化  

Optimination Dijkstra arithmetic for shortest path of urban traffic net

作　　者：张渭军[1] 王华[2] 

机构地区：[1]长安大学地球科学与国土资源学院,陕西西安710054 [2]陕西交通职业技术学院经济管理系,陕西西安710021

出　　处：《长安大学学报（自然科学版）》2005年第6期62-65,共4页Journal of Chang’an University(Natural Science Edition)

基　　金：国家自然科学基金项目(60072044)

摘　　要：在研究城市道路网络特征基础上,建立城市道路网络模型及其数据库,应用一种改进的Dijkstra算法对城市道路进行最短路径查询,该算法是从起点和终点分别用二叉树按起点到终点和终点到起点的方向进行搜索。在计算某一段最短路径时,用Dijkstra算法时间为0.23 s,改进算法时间为0.20 s。仿真结果表明,该算法不仅在时间上有所改进,其时间复杂度由传统Dijkstra算法的O(n2)减小为O(n),而且其所选的最优路径更符合实际,是一种寻求最优路径的有效算法。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 Optlmination 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.

关 键 词：交通工程 道路网络 数据库 DIJKSTRA算法 最短路径 二叉树 

分 类 号：U491.1[交通运输工程—交通运输规划与管理]