最短路问题的Floyd改进算法

目前在不含负回路的网络中,对于求解任意两节点之间最短路问题的方法有很多,Floyd算法是最经典的算法之一,但随着节点数量的增加,重复的计算量也随之增大,从而降低了计算效率。为此,文中通过迭代矩阵和下标标注法对Floyd算法进行了改进,改进后的算法既能快速地计算出网络中任意两节点之间的最短路长值,又能更直观地找出最短路径。通过具体实例分析表明,Floyd改进算法减少了重复计算,简化了路径标注方法,提高了计算效率。     

最短路问题的Floyd加速算法与优化

Floyd算法是求解网络中任意两点之间最短路的高效算法,文章给出了在不含负回路的网络中Floyd加速算法及优化方法,并构造了求解最短路径的序号矩阵。算法分析和计算实例表明,优化后的Floyd加速算法迭代速度快,计算量大大减少,路径寻找简单、直观。     

时延受限组播路由的最短路径加速算法求解

分析了时延受限的Steiner树问题,总结了在构建组播树过程中的代价和计算复杂度变化规律,并根据实际网络环境,从优化最短路径出发,提出了一种基于优化最短路径的时延受限组播路由算法AOSPMPH。该算法以MPH算法为基础,利用Floyd最短路径优化算法求出节点对之间的最短路径,选择满足时延要求的最小代价路径加入组播树,进而产生一棵满足时延约束的最小代价组播树。仿真结果表明,AOSPMPH不但能正确地构造时延约束组播树,而且其代价和计算复杂度与其他同类算法相比得到了优化。     

网络最短路径的动态算法

在通信网络中,两个节点间最短路径的计算是大多数路由算法的基础,对整个网络的性能有重要的影响。该文针对动态变化的网络环境,提出了一种快速的动态最短路径树算法(DMDT),并给出了算法的实现步骤。随机网络模型的仿真结果表明:DMDT算法生成的最短路径树与Dijstra算法基本一致,计算的时间复杂度较Dijstra算法有很大降低。为动态最短路径树的计算提供了一种新的选择。     

双环网络[＋1]边优先最短路径及其寻优策略

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

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

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

基于小世界的无线传感器网络的路由算法

针对小世界的拓扑特性,提出一种基于小世界的无线传感器网络(WSN)的路由算法。该路由算法引入超级节点环概念,将超级节点环视为无向图,利用改进的Floyd算法计算出最短传输路径,缩短路由建立时间,进而提高网络的传输效率,降低无线传感器网络的能耗。仿真结果表明,该算法与针对小世界提出的路由算法PSCF、SWRP和MH相比,在路由建立时间、能量消耗和网络吞吐量方面效果显著。     

基于k-shell的复杂网络最短路径近似算法

复杂网络最短路径经典算法的处理效率较低，不适用于大规模复杂网络，而现有近似算法通用性有限，且计算准确率不理想，不能满足规模日益扩大的复杂网络中的最短路径计算需求。针对于此，提出基于[k]-shell的复杂网络最短路径近似算法。算法利用节点的[k]-shell值进行网络划分并引导搜索路径，利用超点聚合处理[k]-shell子网来降低路径搜索中节点和连边的规模，通过在路径搜索过程使用双向搜索树方法提高算法的计算效率和准确率。实验结果表明，算法通用性较好，在现实与仿真大规模复杂网络中均具有较高的计算效率和准确率。     

基于Cayley图的三维六度环面网络研究

提出了一种三维六度环面Cayley图网络模型.针对该网络模型,给出了一种简单的三维节点编址方案,并利用该编址方案得到了任意两个节点间的最短距离公式;开发了一种简单的分布式最优路由算法,该算法可以运行于网络中的任意节点,可以建立任意两点之间的最短路由路径;基于陪集图(coset graph)理论,给出了一种新型的广播通信算法,并对该算法的效率进行了分析;给出了三维六度环绕网络模型直径的界限值.     

基于Floyd算法的多重最短路问题的改进算法

路径分析是网络分析最基本的问题,其核心是对最短路径的求解。Floyd算法是一种求取最短路的经典算法。分析发现,两点间可能存在多条权重相同的最短路径,而这一点Floyd算法没有涉及。以无向联通图为研究对象,设计了基于Floyd求解多重等价最短路算法,并分析计算了一个实际算例。计算结果表明,基于Floyd的多重等价最短路算法可以有效解决多重等价最短路问题。