Dijkstra算法在室内移动导航最短路径寻址的改进

在室内复杂停车场的路径规划问题上,许多方法使用了单源最短路径的典型算法Dijkstra算法对最短路径进行规划,但该算法需要花费大量时间和空间来计算和存储与最终路径无关节点.为了提高算法效率,通过把地图中所有的结点进行顶点归一、区域集合划分以及区域编号排序等策略,大大提高了算法运行效率.实验显示,在随机对某结点目标进行最短路径搜索时,搜索时间可以缩短80.8%到98.9%,大大减少了时间复杂度和空间复杂度.     

Dijkstra优化算法及其在电子导游中的应用

导游电子化是旅游产业的发展趋势,最短路径搜索是电子导游系统的关键技术之一.经典的Dijkstra算法须花费大量时间用于计算最短路径以外的结点,从而影响了算法的速度.在分析景区结点分布特点和移动设备特性的基础上,对Dijkstra算法进行了优化,优化算法基于对景区结点进行区域划分,缩小了考虑结点的范围,在搜索时仅对相关区域内的结点进行处理,从而提高了算法的速度,最后对优化算法进行了正确性证明和性能分析.     

基于启发式策略的最短路径算法

在讨论经典Dijkstra算法和启发式策略算法（A^＊，矩形算法等）的基础上，提出一种基于Dijkstra算法的动态方向限制搜索算法用于求解道路网络中两节点之间最短路径．该算法结合人类的搜索思路和动态灵活的处理方式，对最短路径算法的搜索策略进行改进，动态改变搜索限制区域，减少计算时间．该算法不仅可以单独提高计算最短路径的效率，而且与其他算法结合起来还可取得更好的效果．实际结果证明动态方向限制搜索算法比经典Dijkstra算法减少近50％的搜索节点数和搜索时间．     

一种最短路径分析优化算法的实现

在对地理信息系统中最短路径分析的实现方案和现有各种最短路径分析算法进行分析、研究的基础上,提出了“优化Dijkstra算法”。该方法使Dijkstra算法的搜索方向明显趋向于目标结点,减少了算法中遍历的结点数,从而提高了搜索速度。总结出两个Dijkstra算法的优化途径：对搜索到的临时标记结点按照最短路径值排序;减小结点的搜索范围即减少永久标记结点的数量。     

深圳应急指挥中心的最优路径规划技术研究

深圳应急指挥中心是一个集指挥、控制、通信、情报、刑侦、探测预警和综合保障为一体的现代化电子信息集成系统,在使用最优路径规划技术上作了很好的尝试.从路径规划的基本原理入手,介绍基于数据结构的最短路径搜索的高效实现方法,并从缩小搜索空间和按地图分层分级搜索的应用策略出发分析路径规划算法.结合深圳的实际情况,给出引入了基数堆、启发式搜索和分级搜索后的路径规划改进Dijkstra算法,提供一个具有很高参考价值的规划技术应用研究.     

一种基于Dijkstra算法的启发式最优路径搜索算法

为了建立一个高效的路径搜索引擎,针对大型应用系统中寻径算法的平衡最优性、时间复杂度以及空间复杂度问题,从经典Dijkstra算法出发,将AI领域的决策机制引入到路径搜索中来,提出了一个启发式最优路径搜索算法.该算法在寻径过程中引入代价函数,由代价函数来决定寻径策略(即优先搜索哪些中间节点),以期望减少搜索节点数.给出了该算法得到最佳解的条件及其证明过程,并且以实例数据对两种算法进行了对比测试.     

移动机器人路径规划算法的研究

路径规划技术作为机器人研究领域中的一个重要分支,是依据某些优化准则,在其工作空间中找到一条从起始状态到目标状态的最优无碰路径.本文针对机器人路径规划技术进行了深入地研究,阐述了机器人路径规划问题的三个子问题等内容,讨论了传统路径规划方法 和基于智能算法的路径规划方法 .本文运用传统Dijkstra算法的贪心策略,针对静态环境下移动机器人路径规划的寻路径子问题,提出了一种改进的Dijkstra路径规划算法.该算法借助具有"先进先出"特点的队列,采用广度优先遍历二维网络结点.该算法在选择邻接结点进行遍历的时候,采用的禁忌策略是禁止访问已经访问的结点,以及被标识为障碍物的结点.实验及分析表明,该算法能准确并快速地寻找到最优路径,且时间复杂度为O(4*n).     

基于权值的Dijkstra停车路径规划算法的优化与实现

基于用户自由选择车位,以停车时间最短为准则,结合权值的计算方法及停车场的内部结构特点,对Dijkstra算法进行改进,设计并实现符合实际的最优停车路径规划算法,并对武汉某公园的大型停车场进行应用验证.结果表明,相对于传统算法,改进后的Dijkstra算法降低时间的复杂度,减少节点的搜索量,提高搜索效率,在停车场引导系统中有一定的实际应用价值.     

大规模网络最大流对偶图算法模型及实现

在网络最大流算法的研究中,为了减少计算量,提出了许多改进的方法.基于图论中的最大流最小割定理,利用网络流图的对偶图的最短路径求网络最大流,对求最短路径的Dijkstra算法进行了研究,给出了一种改进的Dijkstra算法模型,该算法采用了堆排序中的小根堆来选择最短路径结点,使用集合运算对堆中的结点进行处理,使得参加运算的结点数减少,提高了算法的效率.     

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

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