共查询到16条相似文献,搜索用时 78 毫秒
1.
基于Dijkstra算法的一种最短路径改进算法 总被引:1,自引:0,他引:1
本文在Dijkstra算法的基础上,增加了一些数据结构,提出一种能直观地求出从一个顶点到其它各顶点的所有最短路径的算法。 相似文献
2.
3.
通过对问题的分析和假设,建立了线性规划的数学模型,运用Dijkstra算法提供了一个最优的方案,采用Lingo软件得到了全局最优解。 相似文献
4.
城市路径引导系统的一个非常重要的作用就是能动态预测车辆在某路段上的行驶时间,即动态的最短路径。在传统的最短路径预测方法中,往往不能体现出来动态的特点。通过对城市交通路网的建模,利用一种改进的Dijkstra算法可以较好地实现动态路径引导算法。 相似文献
5.
Dijkstra算法的设计与实现 总被引:4,自引:0,他引:4
针对地理信息系统中网络分析的一个关键问题--最短路径分析,采用经典的Dijkstra算法,并在VC环境下实现自定义有向图,主要包括结点和边的绘制与修改,以及权重的更改等功能.能够实现几何网络中任意两结点间的最短路径查找.该程序在单项、双向,以及单双混合网络中都进行了验证,运算结果正确,并具有一定的可行性. 相似文献
6.
殷超 《山东理工大学学报:自然科学版》2010,24(6)
提出基于Dijkstra算法的最短路径搜索改进算法,通过设置高效的优先目标搜索区域,减少大量无意义运算,达到提高搜索效率的目的.以淄博市交通道路图(局部)为例建立系统仿真模型,分别以两点间距离系数和拥堵系数作为权值进行系统仿真,得出了基于不同权值的最短路径求解结果,并对算法改进前后测试数据进行对比分析.结果表明,基于改进Dijkstra算法实际运行时间均值仅占Dijkstra算法运行时间均值的23%以下. 相似文献
7.
Dijkstra算法在嵌入式GIS中的优化实现 总被引:3,自引:0,他引:3
冯欣欣 《北京理工大学学报》2009,29(10):873-876
结合嵌入式系统的特点,对Dijkstra算法进行优化以保证其实时性. 通过对地图数据的分块,改进了直线优化方法. 通过对Dijkstra算法计算过程中已经计算过的结点数据进行临时标记、保存和排序,减少了重复运算. 改进后的寻优过程减少了参与运算的节点,保证了VxWorks系统下路径寻优的速度. 相似文献
8.
基于Dijkstra算法的最短路径的实现 总被引:2,自引:0,他引:2
通过Dijkstra算法编程计算出了青海省西宁市至海东各县之间的最短距离,目的是能为出行的人们提供参考,节省更多时间和交通费用。 相似文献
9.
城市道路最短路径的Dijkstra算法优化 总被引:12,自引:1,他引:12
在研究城市道路网络特征基础上,建立城市道路网络模型及其数据库,应用一种改进的Dijkstra算法对城市道路进行最短路径查询,该算法是从起点和终点分别用二叉树按起点到终点和终点到起点的方向进行搜索.在计算某一段最短路径时,用Dijkstra算法时间为0.23 s,改进算法时间为0.20 s.仿真结果表明,该算法不仅在时间上有所改进,其时间复杂度由传统Dijkstra算法的O(n^2)减小为O(n),而且其所选的最优路径更符合实际,是一种寻求最优路径的有效算法. 相似文献
10.
在分析现有双向Dijkstra算法基础上,通过调整搜索规则,提出了一种改进的用中间链表加速的双向Dijkstra算法,保证了前向和后向搜索在中间相遇,大大地节省了算法的运行时间.经验证,算法的运行效率比传统Dijkstra算法平均提高90%. 相似文献
11.
Dijkstra算法是链路状态路由协议使用的主要算法.随着Intenet中加入的路由器数目的不断增加,该算法运行的时间花费越来越大,影响了路由协议的性能,成为链路状态路由协议的一个瓶颈问题.本文将从这一瓶颈问题出发,采用Intel公司的网络处理器IXP2400为硬件平台,设计Dijkstra算法的硬件多线程实现,从而提高处理器利用率,缓解瓶颈.最后给出一种性能分析和优化的计算方法.通过计算可以看到,在节点比较密集的星形网络拓扑结构中,多线程实现可提高两倍的性能. 相似文献
12.
对二维地表模型运用Dijkstra算法求解最短路径时,为了减少计算量,需要对模型进行简化后,才开始进行Dijkstra算法的求解,所以结果并不符合实际地表情况。不在模型上进行任何简化,而是直接在模型上划分三角网格来处理最原始的模型。然后用基于Dijkstra算法和矢量夹角的三角网格地表模型算法求解最短路径。通过此算法完成了一个实例的最短路径求解。结果表明,采用文中算法所得到的结果符合Dijkstra算法求得的路径和实际情况,而复杂度并没有因为未简化模型而大幅上升,并且算法具有效率高、复杂度低、稳定性好等优点。 相似文献
13.
杨丽娟 《长春师范学院学报》2014,(5):26-29
本文主要利用Dijkstra(迪杰思特拉)算法,将配送中心的三个主要的业务目标,即距离、时间和费用进行整合,建立可实现多目标的模型,使配送中心在线路优化的同时考虑多个因素,实现多种目标。Dijkstra拓展算法还可以进一步拓展,企业可以根据需要在三个目标的基础上进行增减。这种综合考虑多种目标的算法对于实现配送中心线路优化具有现实意义。 相似文献
14.
针对现有大型停车场内泊位诱导的低效问题,基于用户自由选择车位,以停车路径最短为准则,提出Dijkstra改进算法对问题进行分析和求解.并结合实例用VC进行仿真,为入场车辆的停放提供向导,提高停车场管理系统的智能化程度. 相似文献
15.
大规模网络最短路径算法的优化及实现 总被引:1,自引:0,他引:1
求解大规模复杂网络的最短路径问题由于其计算速度慢、需耗费的存储空间大,是与地理信息相关的应用系统经常遇到的瓶颈问题.在深入分析各种常用最短路径算法基础上,基于经典Dijkstra算法,从时间和空间优化角度,实现一种计算任意2点间最短路径的优化算法.初步实验表明,优化后的算法在处理大规模复杂网络的最短路径问题时比经典Dijkstra算法在计算时间上缩短了80%,在耗费的存储空间上减少了将近一倍. 相似文献
16.
针对STEP-NC(standard for the exchange of product data, STEP ; STEP-compliant numerical control,STEP-NC)复杂型腔的刀具路径生成问题,本文提出了一种基于图论和改进Dijkstra算法的STEP-NC复杂型腔最短刀具路径生成方法.在该方法中,首先根据走刀行距和基本元素的等距偏置,生成STEP-NC复杂型腔封闭等距环.然后,基于图论得到封闭等距环的赋权有向图.最后,利用改进的Dijkstra算法生成STEP-NC复杂型腔最短刀具路径.通过实例验证了所提出方法的可行性和有效性. 相似文献