双环网络[+1]边优先最短路径及其寻径策略 被引量：19

1

作者 陈忠学 靳蕃 《计算机研究与发展》 EI CSCD 北大核心 2001年第7期788-792,共5页

双环网络是一种非常重要的互联网络结构 .传统的最优寻径方法没有充分利用这一网络中同一节点到不同节点的最短路径之间的关系 ,所给的算法不是最优的 .定义了双环网络的一种最短路径—— [+ 1]边优先最短路径 ,在此形式下 ,不仅最短路... 双环网络是一种非常重要的互联网络结构 .传统的最优寻径方法没有充分利用这一网络中同一节点到不同节点的最短路径之间的关系 ,所给的算法不是最优的 .定义了双环网络的一种最短路径—— [+ 1]边优先最短路径 ,在此形式下 ,不仅最短路径的形式唯一而且同一源节点到不同目的节点的最短路径之间存在递推关系 .给出了相应的递推公式 ,运用此公式 ,平均不到两次加法运算和一次比较即可找到源节点到所有其它节点的最短路径 .利用所得结果 ,源节点只需存储很少的信息就可以通过简单计算求得到任意其它节点的最短路径 .与传统方法相比 。 展开更多

关键词 双环网络 最短路径 最优寻径 寻径策略 局域网

在线阅读 下载PDF 职称材料

SPFA算法的分析及改进 被引量：17

2

作者 夏正冬 卜天明 张居阳 《计算机科学》 CSCD 北大核心 2014年第6期180-184,213,共6页

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

关键词 组合算法 单源最短路径 SPFA算法 Bellman-Ford算法

在线阅读 下载PDF 职称材料

求带单一限制条件的单源多权最短路径的一个算法 被引量：3

3

作者 孙强 王仁武 黄国兴 《计算机工程》 CAS CSCD 北大核心 2002年第8期135-137,共3页

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

关键词 单一限制 单源多权最短路径 算法 数据结构

在线阅读 下载PDF 职称材料

一种基于桶结构的单源最短路径算法 被引量：4

4

作者 魏文红 李清霞 蔡昭权 《计算机工程与科学》 CSCD 北大核心 2012年第4期77-81,共5页

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

关键词 桶结构 单源最短路径 DIJKSTRA算法 BFM算法

在线阅读 下载PDF 职称材料

基于GPU的单源最短路径算法设计与实现 被引量：4

5

作者 郭绍忠 王伟 +1 位作者 周刚 胡艳 《计算机工程》 CAS CSCD 2012年第2期42-44,共3页

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

关键词 图形处理器 图论 动态数据 单源最短路径 计算统一设备架构

在线阅读 下载PDF 职称材料

深度优先搜索求解网络单源最短路径算法 被引量：2

6

作者 庄明 《小型微型计算机系统》 CSCD 北大核心 2008年第6期1062-1065,共4页

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

关键词 深度优先搜索 单源最短路径 标记法 网络

在线阅读 下载PDF 职称材料

单旋转货架最优拣选路径求解 被引量：2

7

作者 张志强 《北京信息科技大学学报（自然科学版）》 2018年第4期68-72,共5页

对拣选路径优化问题,提出了一种新的路径优化算法。建立了单旋转货架拣选路径数学模型,通过改进的离散粒子群算法求解,通过MATLAB实现算法,并用图论的方法分析和论证了该解决方法的可行性。针对山西某儿童医院的实际应用情况进行建模和... 对拣选路径优化问题,提出了一种新的路径优化算法。建立了单旋转货架拣选路径数学模型,通过改进的离散粒子群算法求解,通过MATLAB实现算法,并用图论的方法分析和论证了该解决方法的可行性。针对山西某儿童医院的实际应用情况进行建模和求解,并在MATLAB中进行仿真,研究证明该算法应用在单回转智能存取系统能够有效求出其运行的最短路径。通过实际应用验证,新的算法能很好求出单垂直循环式药柜的最短路径。该方法为药房自动化控制系统设计提供了有价值的参考。 展开更多

关键词 单旋转货架 拣选路径 优化算法 仿真 最短路径

在线阅读 下载PDF 职称材料

给定费用下单设施点灾民优化安置模型

8

作者 杨建芳 高岩 党亚峥 《计算机应用研究》 CSCD 北大核心 2012年第9期3229-3231,3247,共4页

在地震、洪灾等自然灾害过后,需要及时合理地转移灾民,如何在给定费用下合理安置灾民是救灾工作的重要组成部分。考虑了给定费用下单设施点的灾民安置问题,假设城市道路交通稳定的情况下转换成最短路树来处理,结合反向定位的思想给出数... 在地震、洪灾等自然灾害过后,需要及时合理地转移灾民,如何在给定费用下合理安置灾民是救灾工作的重要组成部分。考虑了给定费用下单设施点的灾民安置问题,假设城市道路交通稳定的情况下转换成最短路树来处理,结合反向定位的思想给出数学模型,以最低费用安置所有的灾民。在此基础上以最小费用改善最大距离贪婪的原则来调整解,使得被安置的灾民离原有设施点的距离加权和尽可能小。通过算例验证了该算法的有效性和可行性。 展开更多

关键词 灾民安置 单设施点 最短路树 贪婪算法

在线阅读 下载PDF 职称材料

基于不含负长度环有向图的Dijkstra算法

9

作者 尹方 邓壮 《重庆邮电大学学报（自然科学版）》 2006年第z1期218-220,共3页

Dijkstra算法是目前公认的较好的最短路径算法,单源点最短路径问题是最短路径问题家族中的核心问题之一。介绍了基于单源点最短路径问题在假定正权有向图上工作的Dijkstra算法以及算法的时间复杂度,同时又介绍了作了功能改进后的Dijkstr... Dijkstra算法是目前公认的较好的最短路径算法,单源点最短路径问题是最短路径问题家族中的核心问题之一。介绍了基于单源点最短路径问题在假定正权有向图上工作的Dijkstra算法以及算法的时间复杂度,同时又介绍了作了功能改进后的Dijkstra算法以及时间复杂度分析,并给出了算法实际工作于不含负长度环有向图的过程和结果。作了功能上的改进后,其算法能正常工作于不含负长度环的带权有向图中。 展开更多

关键词 DIJKSTRA算法 单源点最短路径 正权有向图 负长度环

在线阅读 下载PDF 职称材料

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

10

作者 戴莉萍 黄龙军 《计算机系统应用》 2015年第11期190-194,共5页

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

关键词 单源最短路径 XML树型结构 TREEVIEW控件

在线阅读 下载PDF 职称材料

绿色主干网络中一种高效的节能路由算法 被引量：6

11

作者 陈若宾 王兴伟 +1 位作者 马连博 黄敏 《计算机学报》 EI CSCD 北大核心 2018年第11期2612-2623,共12页

随着互联网规模不断扩大,当前的网络为了能够支持最大的用户访问量并且能够同时保证服务质量,出现了过度供给的情况,正是这种过度供给的现象导致能耗问题日益严重.因此,以降低能耗为目标的绿色互联网的概念被提出,ICT部门也积极投身于... 随着互联网规模不断扩大,当前的网络为了能够支持最大的用户访问量并且能够同时保证服务质量,出现了过度供给的情况,正是这种过度供给的现象导致能耗问题日益严重.因此,以降低能耗为目标的绿色互联网的概念被提出,ICT部门也积极投身于相关研究工作当中.该文基于流量整合的思想,提出了一种高效的节能路由算法,具有节能效率高、节能效果好且不会使优化目标陷入局部最优的特点.该文首先对绿色互联网国内外的研究现状进行了综述和分析,通过对当前节能算法的分析,该文发现目前的一些节能算法容易陷入局部最优解,另外一些算法在寻路的过程中花费了大量时间.针对以上两个问题,该文基于捆绑链路设计了网络模型、功耗参数和数学模型,设计并实现了绿色互联网中的一种高效的节能路由算法.最后该文使用了CERNET2的网络拓扑和实际流量对算法进行了仿真实验和性能评价,并且与最短单一路径优先算法、快速贪心启发式算法进行了对比.实验结果表明,该文设计的算法在真实流量需求下最多可以节省整个网络56.3%的能耗,在节能效果方面相比快速贪心启发式算法有较大幅度的提升,与最短单一路径优先算法相比也有一定程度的提升,在运行时间和路由请求满足率方面也均明显优于快速贪心启发式算法和最短单一路径优先算法. 展开更多

关键词 绿色互联网 路由算法 捆绑链路 最短单一路径优先算法

在线阅读 下载PDF 职称材料

图的Steiner树问题的改进的快速近似算法

12

作者 吕其诚 《黑龙江大学自然科学学报》 CAS 1996年第3期40-42,共3页

设Ｇ＝（Ｖ，Ｅ）是一个边皆有非负权的连通无向图，设Ｚ是Ｇ的结点集Ｖ的子集。一个最小Ｓｔｅｉｎｅｒ树是Ｇ的连通子图，它含有Ｚ的全部结点，且是有最小边权和的树。一个启发式算法结果分别由ＥＩ—Ａｒｂｉ，ｐｌｅｓｎｉｋ和ｋｏ... 设Ｇ＝（Ｖ，Ｅ）是一个边皆有非负权的连通无向图，设Ｚ是Ｇ的结点集Ｖ的子集。一个最小Ｓｔｅｉｎｅｒ树是Ｇ的连通子图，它含有Ｚ的全部结点，且是有最小边权和的树。一个启发式算法结果分别由ＥＩ—Ａｒｂｉ，ｐｌｅｓｎｉｋ和ｋｏｕ等人给出，按该算法得到的Ｓｔｅｉｎｅｒ树与最小Ｓｔｅｉｎｅｒ树最多只差一常数因子２（１—１／ｚ），这里ｚ＝｜Ｚ｜。该算法要计算出ｚ个单源最短路径且算法的时间复杂度为Ｏ（ｚ（ｎｌｏｇｎ＋ｍ）），这里ｎ＝｜Ｖ｜，ｍ＝｜Ｅ｜。现在我们给出了一个改进的算法，其算法性能仍是２（１—１／ｚ），但它只需计算一个单源最短路径且其时间复杂度为Ｏ（ｎｌｏｇｎ＋ｍ），较显著地降低了复杂度的阶数。 展开更多

关键词 图 连通子图 STEINER树 快速近似算法

在线阅读 下载PDF 职称材料

基于Steiner树的模糊最短路径问题的研究

13

作者 赵娜 《洛阳理工学院学报（自然科学版）》 2012年第1期82-85,共4页

在对模糊最短路径分析的基础上,提出了最短路径的改进方案。结合S teiner树的方法,用模糊数代替实数分配给每个边缘,使用了一种新的排序方法求解模糊最短路径。通过实例分析合理地得出问题的最优解,验证了这种方法的有效性。

关键词 模糊排序 单一最短路径 STEINER树

在线阅读 下载PDF 职称材料

两种GPU上改进的最短路径算法 被引量：3

14

作者 刘欣 王非 《计算机应用研究》 CSCD 北大核心 2014年第5期1407-1409,1413,共4页

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

关键词 DIJKSTRA算法 单源最短路径 所有顶点间最短路径 原子锁 二叉堆

在线阅读 下载PDF 职称材料

基于有向图的流式文档逻辑结构重构方法 被引量：4

15

作者 赵林 李宁 彭欣 《计算机工程与设计》 北大核心 2016年第5期1239-1244,共6页

为解决以往流式文档中逻辑结构重构方法的不足,提出一种基于有向图的流式文档逻辑结构重构方法。从模板文档中提取逻辑结构,在此基础上,通过对待查文档中的逻辑标签进行筛选建立有向图,利用有向图的单源最短路径算法过滤多余的逻辑结构... 为解决以往流式文档中逻辑结构重构方法的不足,提出一种基于有向图的流式文档逻辑结构重构方法。从模板文档中提取逻辑结构,在此基础上,通过对待查文档中的逻辑标签进行筛选建立有向图,利用有向图的单源最短路径算法过滤多余的逻辑结构,得到最佳的文档逻辑结构。实验结果表明,该算法能够有效改善逻辑结构识别的准确性,对于文档内容理解和自动化排版与格式检查等应用具有重要意义。 展开更多

关键词 逻辑结构重构 逻辑标签 自动排版格式检查 流式文档 单源最短路径

在线阅读 下载PDF 职称材料

动态规划遵循最佳原理的应用

16

作者 杨格兰 《益阳师专学报》 2000年第6期37-40,共4页

介绍了动态规划算法的基本原理 。

关键词 动态规划 最佳原理 单源最短路

在线阅读 下载PDF 职称材料

基于点云数据的树木骨架线提取研究 被引量：3

17

作者 李杨 李秀峰 《科技创新与生产力》 2017年第6期53-55,共3页

为了构建树木骨架线,利用三维激光扫描仪对树木扫描得到点云数据,以此为数据源,利用Geomagic软件去噪配准后构建树木三维模型,对树木主干、枝干分割后,利用Excel对点云数据进行微分后计算出每一小段的重心即骨架点,最后基于单源最短路... 为了构建树木骨架线,利用三维激光扫描仪对树木扫描得到点云数据,以此为数据源,利用Geomagic软件去噪配准后构建树木三维模型,对树木主干、枝干分割后,利用Excel对点云数据进行微分后计算出每一小段的重心即骨架点,最后基于单源最短路径算法来构建出树木的骨架线,实验证明该方法简单可行,对树木三维建模以及林业研究有重要的意义。 展开更多

关键词 三维激光扫描 点云数据 骨架线 单源最短路径算法

在线阅读 下载PDF 职称材料

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

18

作者 董彬 李全龙 +1 位作者 徐晓飞 宿陆 《计算机科学》 CSCD 北大核心 2006年第11期222-224,共3页

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

关键词 移动目标 单源最短路径树 近似算法 局部图

在线阅读 下载PDF 职称材料

带限制条件的最短路径算法与实现

19

作者 林小玲 何建农 周勇 《福州大学学报（自然科学版）》 CAS CSCD 2004年第z1期43-46,共4页

给出了在GIS环境下带限制条件的单源最短路径算法,该算法是基于二叉堆优先级队列及邻接表的Dijkstra算法.根据用户给出的起始节点和目标节点以及避开节点列和必经节点列,在建立的搜索图中用Ja va语言实现分段查找最短路径.

关键词 单源最短路径 DIJKSTRA算法 二叉堆 限制条件

原文传递

单车型配送问题的研究

20

作者 付彤 郭强 《计算机工程与应用》 CSCD 北大核心 2006年第18期215-217,共3页

针对一般网络上的单车型车辆配送问题,借鉴Floyd算法与节约路径法,构建出了一种在所用车辆数最少的条件下,使总配送里程最短的算法。该算法不但能反映出用车数量,而且同时可以指出配送中心到各用户点运送物资的次序与路径走向。

关键词 配送 最短路径 叶点 单车型 节约算法 FLOYD算法

在线阅读 下载PDF 职称材料