单源路径搜索算法的实现及比较

单源路径搜索算法广泛应用于紧急出警、车载导航、物流配送和管线规划与设计等地理信息系统(GIS)相关领域。而在"连连看"游戏中,需要一种特殊的单源路径搜索方案,对此提出了一种算法,通过记录候选节点的转角数来筛选满足要求的路径。依据这一算法的两种实现策略-宽度优先搜索(BFS)和深度优先搜索(DFS),采用标准模板库(STL)技术,编写了相应的代码,并对这两种策略进行了详细的测试,比较了它们的实际搜索性能。

一种基于桶结构的单源最短路径算法

以单源最短路径为主的最优路径问题是众多社会应用领域内选择最优问题的基础。本文分析了不同实现技术求解单源最短路径问题的算法,结合基于标记设定的Dijkstra算法和基于标记修正的BFM算法的思想,提出了一种基于桶结构的单源最短路径算法。实验结果表明,该算法与前两种算法相比,具有好的运行时间复杂度和可并行性。

基于GPU的单源最短路径算法设计与实现

针对目前图形处理器(GPU)上的动态数据处理问题,在分析现有并行单源最短路径(SSSP)算法的基础上,对GPU上的Moore SSSP算法进行并行化设计与实现。搜索时,综合应用层次化任务分配、层次化工作队列、层次化Kernel调用等策略。在不同类型图数据上进行实验测试,实验结果表明,该算法能有效减少空线程开销、访存开销以及同步时间。

求带多个限制条件的单源多权最短路径算法

带限制条件的多权最短路径问题具有广泛的应用。本文给出一个通过按字典序生成从源顶点到目标顶点的非支配路径的方法 ,求出满足限制条件的最短路径的算法 ,并且分析了算法的时间复杂度。

求带单一限制条件的单源多权最短路径的一个算法

给出了带单一限制条件的单源多权最短路径问题的一个算法,并证明此算法是正确的;该算法中借用了语言的特点,设计了一些C独特的数据结构,这使得该算法设计和实现非常简单。

单源最短路径算法的图示教学设计与实践

单源最短路径是GIS网络分析的一个重点内容,对GIS、空间信息技术等相关专业的学生来讲,由于经典的最短路径算法(Dijkstra)描述较抽象,让学生掌握单源最短路径算法的本质思想较难。提出用图示教学法来教授GIS中单源最短路径算法的基本原理和思路,详细介绍了图示表示的过程,可以为最短路径算法及其应用的教学过程提供参考。

单源最短路径问题的改进算法

探讨了单源最短路径问题算法所能达到的时间复杂性的下界 ,提出了时间复杂性为O(tn+m)和O(nlogt+m)的改进算法 ,其中n =|V|,m =|E|,t为从优先队列中抽取最小结点的次数 ,我们主要用Fibonacci堆和拓扑排序的思想方法。

深度优先搜索求解网络单源最短路径算法

提出在深度优先搜索过程中采用标记当前搜索位置离起始点最短距离方法,有效地实现了求解复杂网络的单源最短路径问题.通过对运算效率的分析,表明该算法通过优化改进可以达到理想的运算效率;模拟了不同规模的含障碍网络（182-13770个节点）,其单源最短路径的求解运算平均效率为O（kV）（其中k≤18,V为路节点数）,等同于用改进后的最优Djkstra算法求解效率O（mlogn）.报告了一个具有现实应用价值和更具潜在研究价值的深度优先搜索智能算法.

单源多路径配装-运输集成模型算法研究

货物配装和运输是物流配送系统的重要组成部分,是提高物流配送系统运作效率的关键。针对物流配送系统的复杂约束,建立了单源多路径配装-运输集成模型。为求解上述模型,采用基于客户点序号编码,最大保留交叉和自适应交叉变异等技术,设计了改进的遗传算法。实例计算表明,模型和算法可行有效,能较好地解算单源多路径配装-运输问题,为物流配送系统的优化提供了新的思路。

基于XML-Tree的单源最短路径改进算法及快速仿真

单源最短路径问题是图论中的一个基础课题.结合图与树在数据结构表示上的相似性及易转换性,基于XML技术提出了一种改进的单源最短路径算法.该算法利用XML结构,按照任意树的生成顺序组织成一棵树;而后对树中的每条边做判断,不断调整当前各个节点到源点之间的最短距离.使用基本控件快速实现该算法的仿真过程,实验结果表明,该算法具有较好的时间效率,灵活性较强、简单易懂及较好的应用价值.

单源最短路径问题的Seidel迭代法

该文提出一种有别于Dijkstra法的Seidel迭代法。虽然在最坏情况下不优于Dijkstra法 。

基于单源最优路径的NOMA中继选择与协作传输

目前,在非正交多址接入(non-orthogonal multiple access, NOMA)中继通信的研究中,中继用户的选择是随机的,并没有考虑中继节点之间信道条件的差异。为了得到信道条件较好的中继用户,提出一种基于单源最优路径的中继选择策略,从基站广播信号以用户为节点,设定信道参数,寻找最佳传输通路。当信号到达目标节点后,基站从目标节点处收集所有可达通路,通过对比各通路的信道参数,选出一条最好的传输通路。基于所提中继选择策略,在非机会式NOMA系统中,提出一种新的协作传输方法,该方法在中继传输过程中剔除了多余信号以降低信号间干扰。仿真结果表明,在相同条件下,采用所提策略的协作传输方法比随机中继选择用户中断概率更低,有效降低了系统复杂度。

移动目标单源最短路径树更新的近似算法

提出一种更新移动目标最短路径树的近似算法来避免重新生成整棵路径树。算法使用了局部图的思想,使每次迭代更新尽量少的节点来减少代价。实验证明算法具有良好的效率、近似度和可伸缩性。分析了如何调整算法,以便在近似度和效率之间实现平衡。

基于最小生成树算法求解图的单源最短路径的研究

对《基于Kruskal算法的最短路径算法研究》一文中提出的方法进行探讨,通过构造实例论证了Kruskal算法并不能直接用于求解有向带权图的单源最短路径问题,并综合性地对基于最小生成树算法求解图的单源最短路径问题进行分析,通过构造实例最终得出最小生成树算法不适用于求解图的单源最短路径问题的结论.

遗传算法在路径规划上的应用

为了满足出行者能高效快捷地到达目的地,需要找到一条综合权值最优的出行路径,再在其上设置指路标志对目的地进行指引.基于此,本文首先根据路网的特点,对交通路网模型进行表述;接着阐述了遗传算法的基本概念和算法思想,并以行驶路程和交叉口个数作为出行者路径选择的因素,定义了行驶路程和交叉口个数综合指标最小的路径为最优路径;最后,以广州大学城中山大学为例,在明确起终点的情况下,利用遗传算法的方法找到了去往中山大学的最优路径,验证了遗传算法在路径规划上的有效性.

最短路径问题的若干算法的编程

本文讨论了带权图的最短路径问题的三类不同情况，针对每种情况介绍了较好的算法，并在MATLAB软件环境下编制了这些算法的程序。通过一个实例，验证了算法的正确性。

两种GPU上改进的最短路径算法

针对图论中的最短路径问题，提出了两种在GPU上改进的最短路径搜索算法，即针对单源最短路径问题的基于迭代方式且采用原子锁优化的Advanced_Atomics-SSSP算法以及针对所有顶点间最短路径问题的采用二叉堆优化的Heap-APSP算法。将两种算法应用到美国公路网图和节点的度均为6的普通图中，通过对算法的测试表明，Advanced-Atomics-SSSP算法的性能依赖于节点的度数，当节点的度数大于6时加速效果明显，当节点度数为1～3时加速效果不明显；而Heap-APSP可以达到46-56倍的加速比，且加速性能不受节点度的影响。

单汇最短路径问题的一种算法

提出单源最短路径的逆问题———单汇最短路径问题 ,并给出相应的算法。

SPFA算法的分析及改进

SPFA(Shortest Path Faster Algorithm)算法是一种对任意有向图求单源最短路径的算法。该算法实现简单,实际运行效果较好,在国内有着比较大的影响力。但遗憾的是,该算法一直缺少正确的理论分析。对该算法进行了分析,指出该算法在不存在源点可达负圈的有向图中,最坏情况运行时间为Θ(|V||E|);在存在源点可达负圈的有向图中,算法将无限运行下去。对此,给出了改进的SPFA算法,对于任意的有向图,该算法能够在O(|V||E|)内运行完毕。最后,从实际运行角度将SPFA算法与其它思想上同源的最短路径算法进行了一系列比较。

一种改进的Dijkstra算法应用于嵌入式GIS系统

在实践中,Dijkstra算法是处理道路网络的最有效的算法之一。但Dijkstra算法每次都需要扫描节点集合中的所有节点,降低了算法效率。通过对前人的成果和嵌入式系统的性能进行研究和分析后,分两步来提高算法效率:第1步通过数据的预处理缩小算法的搜索范围;第2步为每个节点添加属性值、增加前趋表,以辅助算法快速找到一条最短路径。然后将此算法应用于嵌入式GIS系统中,并使用大量的数据进行测试,结果表明改进的算法明显提高了GIS系统的效率。