共查询到16条相似文献,搜索用时 125 毫秒
1.
唐金文 《渭南师范学院学报》2006,21(2):51-54
在GlS领域,对最短路径搜索问题的算法研究和应用属Dijkstra算法.但是,Dijkstra算法通常仅研究计算一条最短路径.文章通过对Dijkstra原始算法的基本原理和步骤进行分析研究,做如下改进:1、从已通过顶点集到未通过顶点集的可能存在的多条最短路径中,不丢弃任何一条最短路径.而Dijkstra原始算法仅在可能存在的多条最短路径中任选其中一条即可;2、Dijkstra算法的每一步骤,不仅要求路径最短,同时还要求经过的顶点最少,从而求出被原始算法忽略的所有可能存在的最短路径;结果最终可以求出带权图中一起始点到其余顶点的所有最段路径. 相似文献
2.
3.
4.
Dijkstra算法的分析与改进 总被引:3,自引:0,他引:3
Dijkstra算法是许多工程解决最短路径问题的理论基础,有着广泛的应用。传统Dijkstra算法在求解单源最短路径时,存在一些不足之处,影响了算法的效率。本文从节约存储空间和提高运算效率方面对传统Dijkstra算法进行了改进,通过分析与比较,这种改进算法的效率优于传统的Dijkstra算法,特别适用于大规模网络。 相似文献
5.
数据结构中最短路径算法的实现 总被引:1,自引:0,他引:1
最短路径算法种类繁多,比较有名的算法包括:Dijkstra算法、Ford算法、Floyd算法、Moore算法、A*算法、K值算法,而即使同一种算法也有多种不同的实现方式。本文介绍了求最短路径的Dijkstra算法的设计思路及Visual C 语言编程实现。实验表明:该算法能高效地求出一个顶点到其它各顶点的所有最短路径。 相似文献
6.
刘朝霞 《佳木斯教育学院学报》2014,(4):160-161,163
Dijkstra算法是最具有代表性的最短路径算法,为解决许多工程领域中出现的最短路径问题提供了理论依据。本文分析了Dijkstra算法以及该算法存在的不足,并提出了优化该算法的方法,通过与原算法作比较,结果表明这种改进的算法在运行时间和效率上得到了提高,其占用的存储空间得到了减少。 相似文献
7.
基于Dijkstra最短路径算法的优化研究 总被引:3,自引:0,他引:3
李健 《渭南师范学院学报》2009,24(5):61-64
最短路径问题是图论研究中的一个重要课题.Dijkstra算法是许多工程解决最短路径问题的理论基础,有着广泛的应用.本文在分析传统Dijkstra算法的基础上,提出该算法在实现方法上存在的一些不足之处,并从节约存储空间和提高运算效率方面对其进行了改进,通过分析与比较,这种改进算法的效率优于传统的Dijkstra算法,具有较好的适用性. 相似文献
8.
9.
李政 《桂林师范高等专科学校学报》2007,21(2):129-131
在求解最短路径时经常使用经典的Dijkstra算法,但在实际应用中在计算最短路径长度时需要进行大量的数据比较,而当图中两顶点之间的距离是∞时,是没有必要进行比较的。本文从存储结构上讨论如何对Dijkstra算法进行优化,尽量减少数据比较次数。 相似文献
10.
孟祥清 《河北能源职业技术学院学报》2002,2(4):78-80
图论中的最短路径问题在计算机技术中应用广泛。求最短路径的方法常用的是由Dijkstra提出的按路径长度递增的次序产生最短路径。此算法用表格计算更为简单。 相似文献
11.
从嵌入式GIS原理入手,对车载智能导航中交通网络建模的关键问题、地图匹配算法流程和导航路径优化算法进行了研究,文中重点探讨了最短路径分析的Dijkstra优化算法。最后借助eSuperMap进行了测试和验证,达到了预期的效果。 相似文献
12.
基于最短路径优化问题Dijkstra算法程序的设计和实现 总被引:1,自引:0,他引:1
在九十年代公认的求最短路径的最好的算法是由E.W.Dijkstra于1959年提出的标号算法,此算法可以很好地解决求最短路径问题,但是该算法采用手工求解,计算量大且很繁琐.本文在此算法的基础上采用矩阵运算的方法,从而实现了完全应用程序求解,在很大程度上解决了上述问题所遇到的难点,使求最短路径和最短距离这两个较复杂的问题变得非常容易求解. 相似文献
13.
娄山佑 《洛阳师范学院学报》2013,32(5)
利用Dijkstra算法求连通网中某一个顶点到其他顶点的最短路径时,修改连通网的存储结构,利用邻接矩阵存储最短路径的同时引入二叉树,提高算法的执行效率. 相似文献
14.
在导航过程中,当最短路径道路上有拥挤、堵塞或中断的情况发生时,利用Dijkstra最短路径算法中的最短路径长度和前驱结点两个辅助向量数据,可迅速在其邻接结点中选择一条新的最短路径。实现了最短路径的动态调整,从而可以尽快地到达目的地。 相似文献
15.
Dijkstra算法的优化 总被引:1,自引:0,他引:1
Dijkstra算法是许多工程解决最短路径问题的理论基础,可用来找出图中指定节点到其他节点的最短距离,有着广泛的应用。文章通过分析传统Dijkstra算法的设计思想,提出该算法在实现方法上存在的一些不足之处,并从节约存储空间和提高运算效率方面对其进行了改进,并通过复杂性分析比较,得出这种改进算法的效率优于传统的Dijkstra算法。 相似文献
16.
最短路径问题在交通、网络应用中具有很高的实用价值,最短路径搜索算法在空间和时间复杂度上有不同的特点,根据需求的现状合理选择搜索算法和改进经典算法是应用中的常规方法。由简单到复杂的分析了搜索最短路径的9种算法,并且比较了经典的Dijkstra算法和启发式搜索算法A*的关系和特点,并且提出了提高搜索效率的改进方法。 相似文献