文献类型：期刊文章

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

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

出　　处：《长安大学学报（自然科学版）》

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

年　　份：2005

卷　　号：25

期　　号：6

起止页码：62-65

语　　种：中文

收录情况：AJ、BDHX、BDHX2004、CAS、CSA、CSCD、CSCD_E2011_2012、EI、IC、JST、RCCSE、SCOPUS、ZGKJHX、核心刊

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

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

分 类 号：U491.1[物流管理与工程类]