共查询到20条相似文献,搜索用时 15 毫秒
1.
基于Dijkstra算法的一种最短路径改进算法 总被引:1,自引:0,他引:1
本文在Dijkstra算法的基础上,增加了一些数据结构,提出一种能直观地求出从一个顶点到其它各顶点的所有最短路径的算法。 相似文献
2.
最短路径分析是网络拓扑中的一个重要的应用,它在地理信息系统、计算机网络路由等方面发挥着至关重要的作用。解决最短路径问题的经典方法是Dijkstra算法,时间复杂度为O(n2),在大数据量下效率低下而且使用邻接矩阵存储图形数据在一定程度上造成了空间浪费。该文在分析了Dijkstra算法的基础上提出来一种改进方法,该法使用STL容器来代替邻接矩阵来存储图形数据提高了查询效率,并且利用双队列来存储节点降低了内循环次数,减少了很多不必要的计算,从而降低了算法时间复杂度。STL容器的应用使得最短路径算法得到了扩展,在求解最短路径的同时还支持添加障碍点,增加开关节点等应用。 相似文献
3.
为了解决海量空间数据的快速网络分析,在分析Dijkstra算法缺点的基础上,提出并详细介绍了一种基于Dijkstra算法的优化算法-邻接结点算法,该算法充分利用了网络拓扑信息中的弧段的连接关系,避免了使用含有大量无穷值的关联矩阵,结果表明:该优化算法可以节约大量的内存,适合海量数据的网络分析.实践证明,该算法对于结点数比较大的网络具有较好的适用性. 相似文献
4.
一种基于城市应急系统的最短路径算法 总被引:1,自引:0,他引:1
城市应急系统(如119火警、110报警以及120急救等)要求在事故发生时,救援者能以最快的速度到达事故现场,而"最短路径"问题是满足该系统需求的关键技术之一。正是针对城市应急系统的这种特点,以消防信息系统为例,在对现有最短路径算法分析研究的基础上,结合G IS技术的应用,提出了一种实时、高效的最短路径生成算法。 相似文献
5.
《天津理工大学学报》2016,(2):40-44
提出一种基于脉冲耦合神经网络(PCNN)的框架来解决随机时变网络最短路径问题.由于随机时变网络中弧的长度是不确定的,因此传统的最短路径算法无法有效的解决随机时变网络最短路径问题,本文中提出的随机时变神经网络(STDNN)算法通过构造具有随机时变特性的神经网络来解决随机时变网络的时变和随机特性.理论和实验分析可以得出,算法针对边较少,结点稠密的随机时变网络求解效率较高. 相似文献
6.
7.
一种求解最短路径路由的遗传优化算法 总被引:4,自引:0,他引:4
吴志祥 《武汉科技大学学报(自然科学版)》2007,30(4):408-411
将可变长度染色体——路由串和它的基因——节点应用于编码问题,交叉操作,在交叉点进行部分染色体(路由串)交换,变异操作,以维持种群的多样性。使用该算法进行简单操作,可以维护好所有不可行的染色体;交叉操作和变异操作相结合,能保证最优解的搜索能力和解的全局收敛性。实验结果证明,该算法收敛快,可靠性高。 相似文献
8.
吴鹏 《贵州师范大学学报(自然科学版)》2012,30(5):69-72,102
在不考虑负回路的前提下,给出了在含有负权的赋权图上求任意两点间最短路径的一种简便算法,此算法既适用于有向图又适用于无向图,并且可据此算法找到最短路径。 相似文献
9.
一种限制搜索区域的最短路径改进算法 总被引:3,自引:0,他引:3
最短路径算法效率是许多应用领域普遍关注和迫切需要解决的问题。该文在深入分析经典Dijkstra最短路径算法优化途径的基础上,从控制路网规模入手,提出了矩形限制搜索区域的最短路径算法。根据路网分布的特点,采取比值系数分段取值的方法,进一步提高了算法效率。原型系统实验显示了改进算法的高效性和可行性。 相似文献
10.
温晓磊 《天津理工大学学报》2009,25(1)
为了解决无向网络的最短路径优化问题,本文采用的是遗传算法和模拟退火算法相结合的思想,阻止早熟现象的发生,保证种群的多样性,防止陷入局部寻优情况的出现,并且定义了无向网络中的结点结构.仿真比较实验说明,混合算法不仅比单一遗传算法运算时间缩短,而且可以找到最短路径,证实了该算法的可行性. 相似文献
11.
基于Kruskal算法的最短路径算法研究 总被引:1,自引:0,他引:1
首先对传统的Dijkstra算法进行分析,然后依据Kruskal算法给出一种求解最短路径的方法,并对该方法的核心思想、具体实现步骤和求解过程进行详细描述,最后通过实例将该方法与Dijkstra算法进行对比,验证该方法的有效性. 相似文献
12.
13.
视频摘要以简短的内容概括原始视频,是对原始视频的浓缩或者总结.传统的视频摘要方法有基于聚类的方法,通过视频帧的局部或全局特征将视频帧分成多个有代表性的集群,在每个集群中提取关键帧,最后去除冗余生成摘要;也有基于图模型的方法,将视频帧作为顶点,连接顶点的边表示帧间的关系,通过图的模块化信息提取关键帧.文章将聚类方法和图模... 相似文献
14.
15.
基于启发式策略的最短路径算法 总被引:6,自引:0,他引:6
在讨论经典Dijkstra算法和启发式策略算法(A^*,矩形算法等)的基础上,提出一种基于Dijkstra算法的动态方向限制搜索算法用于求解道路网络中两节点之间最短路径.该算法结合人类的搜索思路和动态灵活的处理方式,对最短路径算法的搜索策略进行改进,动态改变搜索限制区域,减少计算时间.该算法不仅可以单独提高计算最短路径的效率,而且与其他算法结合起来还可取得更好的效果.实际结果证明动态方向限制搜索算法比经典Dijkstra算法减少近50%的搜索节点数和搜索时间. 相似文献
16.
关于最短路径算法 总被引:2,自引:0,他引:2
肖金声 《中山大学学报(自然科学版)》1987,(3)
本文先为两个经典的最短路径算法补充具体路径的保留办法。然后,提供一个便于实现的求有向图两点间所有路径的算法. 相似文献
17.
基三网络中一种最短路径路由算法 总被引:1,自引:1,他引:0
Min-DDRA在DDRA路由算法的基础上结合中转节点的设计思想,实现了一种最短路径路由算法.该算法兼有传统基于路由表算法和DDRA路由算法的优点.基于真实网络负载的实验结果表明,与DDRA路由算法相比,Min-DDRA路由算法性能提高了2%~3%,功耗降低了3%~6%. 相似文献
18.
最短路径算法是计算机科学与地理信息科学领域的研究热点。本文对常用的最短路径标号算法进行了分析,并讨论了优化算法的方法。 相似文献
19.
针对单源最短路径Dijkstra 算法效率低的问题, 基于地理信息系统(GIS: Geographic Information System),提出距离均衡的社区分析网络分割方法。将GIS 中道路网络分割降解为距离均衡的社区网络, 再利用限制分层算法, 通过淘汰不太可能出现在最短路径上的节点, 限制GIS 中最短路径的搜索区域, 以降低算法的复杂度。实验结果表明, 优化后的算法可有效减少搜索节点数, 与经典算法相比, 其运行效率有所提高。 相似文献
20.
D算法(Dijkstra,狄杰斯特拉算法)是典型的单源最短路径算法,用于计算一个节点到其它所有节点的最短路径。从存储结构角度,提出一种优化D算法的最短路径方法,利用基于COMArcEngine技术加以实现。 相似文献