共查询到20条相似文献,搜索用时 0 毫秒
1.
以单源最短路径为主的最优路径问题是众多社会应用领域内选择最优问题的基础。本文分析了不同实现技术求解单源最短路径问题的算法,结合基于标记设定的Dijkstra算法和基于标记修正的BFM算法的思想,提出了一种基于桶结构的单源最短路径算法。实验结果表明,该算法与前两种算法相比,具有好的运行时间复杂度和可并行性。 相似文献
2.
We consider the problem of updating a single-source shortest path in either a directed or an undirected graph, with positive
real edge weights. Our algorithms for the incremental problem (handling edge insertions and cost decrements) work for any
graph; they have optimal space requirements and query time, but their performances depend on the class of the considered graph.
The cost of updates is computed in terms of amortized complexity and depends on the size of the output modifications. In the case of graphs with bounded genus (including planar graphs),
graphs with bounded arboricity (including bounded degree graphs), and graphs with bounded treewidth, the incremental algorithms
require O(log n) amortized time per vertex update, where a vertex is considered updated if it reduces its distance from the source. For general
graphs with n vertices and m edges our incremental solution requires O(
log n) amortized time per vertex update. We also consider the decremental problem for planar graphs, providing algorithms and data
structures with analogous performances. The algorithms, based on Dijkstra's technique [6], require simple data structures
that are really suitable for a practical and straightforward implementation.
Received January 1995; revised February 1997. 相似文献
3.
给出了模糊网络期望最短路径问题的定义,提出一种并行模糊神经网络最短路径(PFNNSP)算法解决模糊网络最短路径问题。PFNNSP算法首先通过模糊模拟对网络中的边权进行估计,接下来脉冲波在神经元之间的并行传播,相互激活搜寻任意一对结点之间的最短路径,最后,算法回溯输出路径表示和路径长度。在随机生成的小规模数据集上的仿真实验表明,PFNNSP算法在边权服从三角模糊分布的网络中执行时间优于Dijkstra算法,在大规模路网信息数据集上的仿真实验表明,PFNNSP算法能够有效求解网络中的最短路径,并且算法在迭代次数和收敛速度上要优于Dijkstra算法和A*搜索算法。 相似文献
4.
单源最短路径问题是图论中的一个基础课题.结合图与树在数据结构表示上的相似性及易转换性,基于XML技术提出了一种改进的单源最短路径算法.该算法利用XML结构,按照任意树的生成顺序组织成一棵树;而后对树中的每条边做判断,不断调整当前各个节点到源点之间的最短距离.使用基本控件快速实现该算法的仿真过程,实验结果表明,该算法具有较好的时间效率,灵活性较强、简单易懂及较好的应用价值. 相似文献
5.
6.
定义了长廊为平面上由一序列凸四边形构成的有界连通区域,提出长廊最短路径问题,并给出求长廊最短路径的一个算法,最后证明该算法的正确性和在最坏情况下的最优性。 相似文献
7.
8.
《Journal of Parallel and Distributed Computing》1995,24(1):94-99
We present an optimal parallel algorithm for the single-source shortest path problem for permutation graphs. The algorithm runs in O(log n) time using O(n/log n) processors on an EREW PRAM. As an application, we show that a minimum connected dominating set in a permutation graph can be found in O(log n) time using O(n/log n) processors. 相似文献
9.
本文以时间代价作为目标函数,针对复杂网络的优化问题进行研究,给出了目标评价函数模型的建立过程,提出了改进的A*算法求解复杂网络中最短路径问题的算法,并以城市交通为例,对算法进行了验证,实验结果表明所提出的算法可适用于一般多重图中最短路径问题的快速求解,具有广泛的应用价值。 相似文献
10.
针对含有n个区间的区间图K-连接最短路径(K-SP)问题,提出一种求解区间图K-SP问题的在线算法。分析区间图及其最短路径问题的特有性质,利用改进的动态规划算法和贪心算法,优化在线算法的时间复杂度。理论分析结果表明,该算法的时间复杂度为O(nK+nlgn),与目前已知最优的离线算法复杂度相同。 相似文献
11.
一种改进的蚁群算法求解最短路径问题 总被引:25,自引:3,他引:25
蚁群算法是一种新型的模拟进化算法,为求解复杂的组合优化问题提供了一种新的思路。该文应用蚁群算法求解最短路径问题,对算法的选择策略、局部搜索、信息量修改三方面进行改进,使算法不易陷入局部最优解,并且能较快地收敛到全局最优解。实验结果表明,改进方法是合理的、有效的。 相似文献
12.
迷宫最短路径问题新算法 总被引:1,自引:0,他引:1
提出了求解迷宫最短路径问题的新算法,该算法抛弃了经典算法(深度优先搜索和广度优先搜索)中繁杂低效的递归、回溯思想。通过合理的变换,将原问题转化为迷宫路径深度图的生成问题。最后对算法进行了严谨的分析和实例测试,显示出该算法易于理解、易于编程、时间空间复杂度低等优点。 相似文献
13.
用图论的方法对最短路径问题进行数学描述,分析了单源最短路径Moore和Dijkstra 两种算法对多处理机系统在图的搜索阶段的并行性差异;提出了Moore算法在多处理机系统中高效并行实现的两种切实可行的方案。 相似文献
14.
提出一种更新移动目标最短路径树的近似算法来避免重新生成整棵路径树。算法使用了局部图的思想,使每次迭代更新尽量少的节点来减少代价。实验证明算法具有良好的效率、近似度和可伸缩性。分析了如何调整算法,以便在近似度和效率之间实现平衡。 相似文献
15.
16.
求受顶点数限制的最短路径问题的一个算法 总被引:8,自引:1,他引:8
提出了求受顶点数限制的最短路径问题的一个算法,与现有的算法相比,该算法效率较高,时间复杂度为O((k-2)m^2)(k是受限制的顶点数,n是图中顶点总数),而且该算法比较简单,易于描述,实现和理解. 相似文献
17.
A Primal-dual Neural Network for Shortest Path Problem 总被引:1,自引:0,他引:1
The shortest path (SP) problem is a classical combinatorial optimization problem which plays an important role in a packet-switched computer and communication network. A new primal-dual neural network to solve the shortest path problem (PDSPN) is presented in this paper. The proposed neural network combines many features such as no network coefficients set,easy implementation in a VLSI circuit, and is proved to be completely stable to the exact solutions. The simulation example shows its efficiency in finding the "optimum" path(s) for data transmission in computer and communication network. 相似文献
18.
杨雷 《数字社区&智能家居》2009,(13)
单源最短路问题是算法研究中由来已久的一个问题,在算法领域早期已经得到了较好的解决,但是在应用计算机语言实现的过程中往往不够优化,导致较高的时间复杂度和空间复杂度。从原始的迪杰斯特拉算法入手,进行透彻分析,在算法思想和实现方式上提出一种全面优化的算法方案,并给出了核心代码。实现过程中使用了堆的数据结构,并在具体的实现过程中进行灵活的优化。经过理论的算法复杂度分析,以及实际的数据测试,都证明全新优化后地单源最短路算法计算耗时非常少,空间复杂度也得到很大程度的降低,应用价值更强。 相似文献
19.
杨雷 《数字社区&智能家居》2009,5(5):3439-3442
单源最短路问题是算法研究中由来已久的一个问题,在算法领域早期已经得到了较好的解决,但是在应用计算机语言实现的过程中往往不够优化.导致较高的时间复杂度和空间复杂度。从原始的迪杰斯特拉算法入手,进行透彻分析,在算法思想和实现方式上提出一种全面优化的算法方案,并给出了核心代码。实现过程中使用了堆的数据结构,并在具体的实现过程中进行灵活的优化。经过理论的算法复杂度分析,以及实际的数据测试,都证明全新优化后地单源最短路算法计算耗时非常少,空间复杂度也得到很大程度的降低.应用价值更强。 相似文献