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

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

双环网络的[+h]边优先寻径策略

提出一种先走[ h]边、当走[ h]边不利时才走[ 1]边的[ h]边优先寻径策略;得出[ h]边优先最短路径和双环网络的"竹筏"(一种新L形瓦)型空间解;"竹筏"中节点之间的[ h]边优先最短路径存在递推关系;由节点的[ h]边优先最短路径推出双环网络的直径公式;利用VB6.0和SQLServer2000仿真了[ h]边优先寻径策略;作者曾提出的[ 1][ h]双边寻径策略是固定路径,寻找节点,而[ h]边优先寻径策略是固定节点,寻找路径;传统L形瓦难以构造但易求其等价双环网络的直径,而新L形瓦易构造但难以求其等价双环网络的直径;指出了陈忠学文中的几个错误.     

基于层的双环网络G(N;h)的最短路径算法

提出基于层的方法来研究双环网络G(N;h)路由特性;给出基于层的路由策略;给出了双环网络G(N;h)直径等于其树型结构的最大层数的重要结论;研究了双环网络G(N;h)的最短路径问题,给出了0节点到其它任意节点的最短路径算法.并利用面向对象的Java语言实现了这一算法.     

一类双环网的特征分析及寻径控制

本文首先提出双环网中任意节点之间的最短路径求取方法，而后针对一类跨度为ｈ（≤Ｌ√」＋１）的双环网进行拓扑分析（Ｎ为网络规模），并构造了一个十分简便的最优寻径算法，最后给出一个容错寻径算法。     

基于节点压缩的寻径优化算法

最短路径问题是一个经典问题,而目前的研究大多是针对给定起点和终点,选择从起点到终点的最短路径,且取得了不少成果。而对于限定时间的最短路径问题的研究成果相对较少,这类问题在现实生活中却随处可见。针对这一问题提出几种限定时间的寻径优化算法,从对回溯法的改进到不同的节点压缩的方法,给出改进的回溯法以及三种基于节点压缩的寻径算法。算法实现在限定的时间内从起点出发经过给定的节点集合再到达终点的路径选择,并针对不同复杂度的网络图有相应合适的算法可以选择,从而有效地解决这类问题。     

一种新的Kth最短路径搜索算法

借助于“背离”路径的概念,论文在2nd最短路径搜索算法的基础上提出了一种新的Kth最短路径搜索算法,并将其应用至实际环境中。通过K-1次2nd最短路径搜索算法的迭代,该算法可以求出网络中任意两个给定节点之间的Kth最短路径,2nd最短路径搜索算法在计算上具有简单性,因而也同样具有简洁、快速的特点。     

网络最短路径的一种更新策略

求解最短路径问题被广泛用于求解现实中的搜索相关问题。然而现实瞬息万变,一个连通网络的节点常常发生变动,而一旦发生改变,传统算法必须再次计算从源点到各节点的最短路径。然而虽然节点发生了变动,可是最短路径却未必全部发生了改变,这就造成了不必要的浪费。鉴于此提出一种基于Dijkstra算法的最短路更新策略,将Dijkstra算法做了改进,使其不必重新计算也能在连通图发生改变的时候更新最短路径。     

有向赋权网络中任意节点对的最短路径集求解方法

有向赋权网络任意节点对之间的最短路径可能多于一条,运用Floyd算法对已知加权交互网络的最短路径进行求解,对获得最短路径后的每一个节点对,向其中插入已知交互网络中的其余所有节点,并计算此时的节点对之间的路径,通过与前次Floyd算法计算出的最短路径进行比较,筛选出构成最短路径的所有中间节点,并构建路径支撑树,基于路径支撑树确定任意节点对的最短路径集.     

时序最短路径算法

最短路径是指网络中两结点间阻碍强度最小的一条路径。传统的最短路径是在静态网络上进行研究的,然而现实生活中很多网络是动态的、有时序性的,因此传统的最短路径算法并不能用于解决所有最短路径问题。为了寻找时序网络上的最短路径,在Dijkstra算法思想基础上,提出一种时序最短路径的精确算法。文中利用严格的数学推导证明了本算法的可行性,并通过对构建的网络做实证分析验证了算法的正确性。     

传感器网络定向扩散机制中梯度生成算法的研究

如何生成优化的梯度是传感器网络定向扩散中的一个关键问题,本文在分析一种基本梯度生成算法的问题基础之上,利用兴趣包的转发次数对其进行改进,设计了一种分布式的最短路径梯度生成算法.该算法极大的降低了邻居节点间建立"平行梯度"和"逆向梯度"的概率,可构建从源节点到sink节点的多条最短路径.仿真表明,改进的算法可建立更为有效的梯度,从而使得定向扩散中数据报文沿着更短的路径传输,无线传感器网络的能量利用率更高.     

基于最简子图的链接表示及预测

稀疏网络的传统链接预测准确率低,为了捕捉稀疏网络节点间建立链接的可能性,提出基于节点间最短路径的最简子图概念。最简子图反映了节点间的拓扑紧密关系,在采用node2vec节点向量化方法的基础之上,实现了基于最短路径的链接表示,并采取长短期记忆循环神经网络(LSTM)学习长链接节点序列的特征,最终实现链接的分类。实验结果表明,该方法与已有方法相比,在4种不同数据集上的预测AUC值平均提高了11.6%,AP值平均提高了13.3%。     

交换超立方网中的最短路径路由算法

针对交换超立方网络的最短路由问题,提出一个交换超立方网中的最短路径路由算法.利用图论的方法,通过引进子网的概念,研究交换超立方网的拓扑性质,给出节点各边可进行最短路径路由的充要条件,得到其时间复杂度为O(s+t)2).理论分析和仿真结果表明,该算法可输出交换超立方网中任意两节点间的一条最短路径.     

基于半边数据结构的最短路径算法及其实现

在分析传统最短路径算法数据结构的基础上,提出并实现了一种以半边数据结构存储网络拓扑数据的最短路径算法。该算法充分利用半边数据结构存储格式紧凑、操作直观高效等方面的优点,采用较传统方法不同的路径检索方式,实现了快速计算网络中任一结点到其他所有结点的最短路径。实验表明,基于半边数据结构的最短路径算法可以大幅度提高网络中最短路径的计算效率,其性能在网络结点显著增多时愈加明显。     

Dijkstra的一种改进算法

在Dijkstra算法的基础上,该算法使用了一些独特的数据结构(如:前趋表和最短路径表);使用该算法能高效率地求出图中一个顶点到其它各顶点的所有最短路径。用C语言设计了相应程序验证了此算法。     

切换到高一层路网最近四个点的最短路算法

针对基于大规模图的最短路问题求解速度慢的问题,提出了一个基于路网等级的求最短路的快速近似算法。该算法首先求出高一层路网到起点的4个最近点和到终点的4个最近点及最短路径,由高一层路网形成的子图T再加上这8个最短路径形成图T',在T'上求起点到终点的最短路。这种设计使得该算法适合在超大规模图上求解,理论上也证明了精度可控,同时预处理数据也是可行的,从而使两点间最短路的求解速度大大提高。在纽约公路网上的测试结果说明了该算法的有效性和合理性。     

一种不需记录后继的扩展SPT动态更新算法

动态SPT算法是在图的拓扑改变时,以原有SPT为基础作局部更新;SPT动态更新需要解决寻找因为该改变而需要修正最短路径的相关节点的问题。对于传统的SPT定义先扩展,使节点记录距离相等的一条或多条最短路径,称之为ESPT。提出了一种不需记录后继的ESPT动态更新算法并加以证明,通过证明还说明在ESPT定义下该算法找到的所有节点都是动态更新所必要且充分的。给出算例,列出操作过程,对不同复杂度的图进行计算实验,将其结果与经典静态算法进行了对比。     

基于最短路径的多子网链路层拓扑发现算法

针对当前基于地址转发表实现链路层拓扑发现的典型算法在复杂多子网环境下应用存在的问题,提出利用下行链路完整地址转发表构建并优化同一子网交换设备间的最短路径,实现链路层拓扑自动发现的算法。经理论和实际环境验证,证明该算法可以较好地发现复杂多子网链路层拓扑结构,具有较强的实践意义和推广价值。     

基于链路信息的卫星网络最优路径选择策略

分层卫星网络路由协议在通信时比单层卫星网络有更好的表现,但是同样有着一些缺点。快照的频繁切换导致计算开销大、链路拥塞和节点失效时处理能力较差。针对LEO/MEO卫星网络的特点,提出了一种新的路由协议。计算相邻卫星间的实际通信开销,和预估可选卫星到目的卫星间的通信开销,在保证一定链路利用率和低延时的情况下,选择一条最优路径。当链路切换或节点失效时,缩小路径搜索区域,无需重新计算源卫星节点到目的卫星节点路径,只更新部分失效节点,减少计算开销。通过仿真发现,该算法在路径建立以及链路拥塞等方面具有良好的性能。     

求最短路径的新算法

本文提出了一种求最短路径的新算法，并用C语言设计相应的程序验证了此算法。实验表明，该算法能高效地求出一个顶点到其它各项点的所有最短路径。     

所有最短路径的求解算法

本文提出了一种求所有最短路径的算法，能高效地求出一个顶点到其它各顶点的所有最短路径。此外，我们用C语言设计的相应程序验证了此算法。