共查询到20条相似文献,搜索用时 78 毫秒
1.
改进的Dijkstra最短路径算法及其应用研究 总被引:6,自引:1,他引:5
求最短路径是一个应用很广泛的问题。求最短路径的算法有很多,公认较好的算法是Dijkstra标号法。但实验结果表明,Dijkstra标号法有需要改进的地方:①其退出机制对不联通的有向图是无效的,会陷入死循环;②没有涉及最短路径上顶点的邻接点(特指前面的相邻点)问题;③没有涉及多个顶点同时获得p标号的问题。针对上述问题,对标号法进行了改进。算法实验表明,改进的标号法能够有效解决上述问题。在上述工作的基础上,开发了"北京市道路最优路线选择系统",以提供起点和终点之间的最优路线,帮助用户选择出行路线,使市民能够避过交通最拥堵的路段,节约出行时间。 相似文献
2.
《电子制作.电脑维护与应用》2015,(7)
优秀的城市公交网络出行路线图的制定首先应该站在公交乘客的角度上进行研究,在对城市公交网络路线最短路径算法的基础上,同时充分的利用地理信息系统,对公共交通网络中进行两个结点间的最佳路线的选择,通过此路线能够达到最大程度的减少换车的次数。本文充分探讨了基于地理信息系统的城市公交网络出行路线的最佳选择。 相似文献
3.
4.
5.
6.
针对团队出行过程中因信息孤岛导致出行路径非优化和延时等待等问题,提出了一种以团队成员信息共享为基础,以集中式计算为手段的协作式路径优化算法。该算法统筹考虑成员间会合的便捷性、路径/时间最短化等多种因素基础上,通过引入团队会合优先度因子对路径计算进行加权处理,从而实现整个团队出行路径的最优化。理论分析表明,协作式路径优化算法的计算复杂度随团队成员的数量线性增长,与传统的最短路径算法计算复杂度基本相当。仿真结果表明,会合优先度因子值的高低,将会影响会合点及出行路径的选择,因此,可根据实际需求设置会合优先度因子,实现团队会合和路径最短化的动态均衡。最后,以协作式路径优化算法的一个具体的工程应用,阐述团队成员间如何提供支持和帮助,从而安全、高效和有序地到达目的地。 相似文献
7.
肖海俊 《计算机应用与软件》2011,(9)
将Dijkstra的最短路径算法应用到交通运输,对用户出行的路线选择提供指导。将现实中跟地理位置有关的数据转变为适合算法处理的数据结构,并对原有算法进行了存储结构方面的改进。计算路段的权值时不仅仅考虑其长度,而且考虑到了拥塞状况,加入了动态变化的拥塞系数,使这一权值更加合理。 相似文献
8.
总结国内外一些最短路径并行计算算法目前的主要研究结果,并从QoS路由选择目标中的一些方法特点对动态路由优化算法进行改进,使用最短路径并行计算是解决动态路由优化的计算量问题的方法之一,并提出了最短路径并行计算算法优化路由策略的实验方法. 相似文献
9.
10.
公交网络最优路径查询功能是智能公交系统的重要组成部分,求解公交网络最优路径是进行公交系统规划的一项关键技术.通过分析乘客出行选择公交线路所考虑的因素,提出了公交导乘最佳路径算法.在引入公交导乘网络数学描述的基础上,给出了公交导乘最少换乘算法.然后以换乘次数最少、出行距离最短为约束条件,对最短路径算法(Dijkstra算法)进行改进,得出综合考虑路径长度和换乘的最佳公交导乘算法.在深圳市公交网络测试应用的结果表明此算法可行、高效. 相似文献
11.
王华 《计算机与数字工程》2012,40(4):22-23,129
通过实例对比分析Dijkstra算法和Floyd算法特点及适用性,选用Dijkstra算法计算物流配送的最短路径,给出Dijkstra算法求解最短路径问题的实现方法及步骤并集成了一个小型系统,使用随机生成的数据进行最短路径求解,将生成的最短路径在随机生成的图上进行演示,并计算出两种算法执行时间,以期对物流配送中点对点的最短路径有所帮助。 相似文献
12.
13.
14.
15.
构建最短路径树是动态网络研究的重要问题之一。在动态网络中,当边状态发生变化时会引发最短路径树动态的重新构建,反复地计算不仅消耗大量时间,也会导致最短路径树的频繁变化。提出一种稳定的最短路径树构造算法,使得构造的路径树在动态网络上更稳定,即更新最短路径树所需的操作数更少。该算法通过记录频繁变化的不稳定边并尽可能避免将其加入最短路径树中,从而能够高效地减少边变化带来的操作。实验结果表明,与传统的动态最短路径树算法相比,该算法可以得到更稳定的最短路径树,并且更新时间减少了57.24%,结点更新次数降低了43.6%。 相似文献
16.
公交车网络的最短路径算法及实现 总被引:3,自引:0,他引:3
最短路径问题是图论研究中的一个经典算法问题.旨在寻找图中任意两结点之间的最短路径。一般在交通道路网络中最短路径问题就是单纯地求解两点问的最短路径。为了保证实用性,公交车网络的最短路径算法以转车次数最少为首要目的。文中借鉴广度优先搜索的思路来求解最短路径,即逐个找出经过起点站和终点站的车次以及这些车次沿途可转的车次。首先说明了算法的计算机实现方法,再举例详细说明其过程,最后指出此算法的扩充用途。 相似文献
17.
于方 《计算机工程与应用》2011,47(10):197-200
为降低求解三角网格表面任意两点间近似测地线长度和路径问题的时间开销,提出一种基于局部细分法的并行近似测地线算法。采用类矩阵乘最短路径并行算法求解点对间初始最短路径,并用源分割法映射子网格数据;所有处理器并行执行,对其所拥有点对之间的初始最短路径周围三角面片上的边进行细分操作;最后基于局部细化后的细分图并行,求得所有点对间的近似测地线长度和路径。实验结果表明,该并行近似测地线算法能够有效降低求解该类问题的计算时间,计算效率大大提高。 相似文献
18.
一种新的Kth最短路径搜索算法 总被引:1,自引:0,他引:1
借助于“背离”路径的概念,论文在2nd最短路径搜索算法的基础上提出了一种新的Kth最短路径搜索算法,并将其应用至实际环境中。通过K-1次2nd最短路径搜索算法的迭代,该算法可以求出网络中任意两个给定节点之间的Kth最短路径,2nd最短路径搜索算法在计算上具有简单性,因而也同样具有简洁、快速的特点。 相似文献
19.
顾运筠 《计算机应用与软件》2008,25(4):246-248
介绍了GIS领域最短路径搜索的一种优化模式.在Dijkstra's算法的基础上,从三个方面改进了最短路径的计算.首先引入了多级路线图,在读取线路数据时,根据路线的级别有所选择;其次,在计算最短距离时考虑速度的影响;最后,在道路的转弯处,引入虚拟路径来估算转弯对汽车行驶的影响.应用以上三种方法的实验,取得了很好的效果. 相似文献
20.
《Computers & Mathematics with Applications》2005,49(2-3):263-270
In the past, the fuzzy shortest path problem in a network has attracted attention from many researchers for its importance to various applications. In this paper, we propose a new algorithm to deal with the fuzzy shortest path problem. It is composed of fuzzy shortest path length procedure and similarity measure. The former is presented to determine the fuzzy shortest path length from source node to the destination node in the network, and the latter is used to measure the similarity degree between fuzzy length sets. This algorithm not only can yield shortest length but also can offer the actual shortest path to decision makers. An illustrative example is also included to demonstrate our proposed algorithm. 相似文献