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

被引：53

作者：

张渭军 ^{[1
]}

王华 ^{[2
]}

机构：

[1] 长安大学地球科学与国土资源学院

[2] 陕西交通职业技术学院经济管理系

来源：

长安大学学报(自然科学版) | 2005年 / 06期

关键词：

交通工程; 道路网络; 数据库; Dijkstra算法; 最短路径; 二叉树;

D O I：

10.19721/j.cnki.1671-8879.2005.06.015

中图分类号：

U491.13 [];

学科分类号：

摘要：

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

引用

页码：62 / 65

页数：4