城市道路最短路径的Dijkstra算法优化 (2005年)

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