最短路径算法的比较

本文介绍了三种最短路径算法及其算法步骤，这三种算法分别被称为Ｄｉｊｋｓｔｒａ算法、ＰＳＰ算法和ＤＢＦＳ１算法。文中对这三种算法的比较，着重阐述了作为一种在计算机上非常优越的算法ＤＢＦＳ１算法的优越性及其原因。最后，给出了ＤＢＦＳＬ１算法的流程图。     

多目标最短路径进化求解方法

提出一种无圈有向图条件下的多目标最短路径进化算法。使用变长染色体对路径编码。进行染色体适应值分配时同时考虑支配关系及密度信息，保持了种群的多样性。有界精英保留策略保证了算法的优化性能。对算法的收敛性进行了证明。理论分析和实验表明，该算法可以在较短时间内获得多条多目标优化路径。     

基于Mobius立方体的最短路径路由算法

Mobius立方体是超立方体的一种变形结构。Mobius立方体除了具有超立方体本身的可扩展性和路由简单等优点外,它与含有相同数目的点和边的超立方体相比具有更好的性能。文中提出一种新的用于Mobius立方体网络的最短路径路由算法,避免了递归调用。分析和实验证明,相对于Cull P提出的最短路径算法有更高的效率,并易于硬件实现,且时间复杂度为O(n)。     

模拟退火算法求解最短路径填挖问题

在大型的工程和建筑项目中，经常要进行场地平整工作。这引出了一个最短路径填挖问题，目标是找到一个最小车辆路径，使得整个施工过程的总运输距离最短。该问题属于NP—hard问题。本文采用模拟退火算法求解该问题。最后通过算例计算，并同贪婪算法的求解结果进行比较，验证了模拟退火算法的高效性。     

典型城市路网中的椭圆最短路径算法

提出了一种高效可靠的限制搜索区域的最优路径算法．该算法是基于典型城市路网的共同特征, 而不是某个特定城市的统计信息提出的, 它可以应用在不同的城市路网中．针对从源站点到目的站点不同的欧式距离, 算法分别在两类不同大小的椭圆内搜索最短路径．理论计算和实验结果都表明, 当源站点和目的站点相距较远时, 与椭圆限制搜索区域算法相比, 该算法可以降低33%-47%的时间复杂度, 而不会影响查询结果的准确性．     

关于最短路径问题的一种有效算法

经典的关于最短路径算法是基于图的搜索思想的.Dijkstra提出的单源点最短路径和所有顶点对之间的最短径算法就是较为成熟的经典算法.但人们在长期的使用过程中感到其算法结构过于复杂且效率较低.对Dijkstra最短路径算法进行了改进,提出了WY-Dijkstra算法.改进后的算法不实施Dijkstra算法的重复循环,而是作映射或链接处理,从而提高了效率.这一算法适合于复杂的智能系统的应用.     

基于Mbius立方体的最短路径路由算法

Mbius立方体是超立方体的一种变形结构。Mbius立方体除了具有超立方体本身的可扩展性和路由简单等优点外,它与含有相同数目的点和边的超立方体相比具有更好的性能。文中提出一种新的用于Mbius立方体网络的最短路径路由算法,避免了递归调用。分析和实验证明,相对于Cull P提出的最短路径算法有更高的效率,并易于硬件实现,且时间复杂度为O(n)。     

基于带宽剩余率的脉冲耦合神经网络最短路径算法

利用脉冲耦合神经网络（pulse coupled neural network, PCNN）寻找最短路径是一种非确定性算法,运算的复杂度只和最短路径的长度有关,和路径图的复杂程度无关。已有的PCNN最短路径算法只考虑路径长度,而未考虑其他参数,如带宽和时延等。这里除了考虑路径长度,同时考虑实际中带宽剩余量对网络的影响,提出了一种基于带宽剩余率的最短路径算法,用带宽剩余率参数来控制神经元阈值,寻找最短路径。仿真结果表明,该算法可以寻找到全局最优解。     

面向社团结构划分的最短路径相异性指数算法

用最短路径距离取代网络中用布朗微粒衡量的两节点之间的距离,在此基础上提出了基于最短路径的相异性指数算法.对算法实现过程进行描述,并将算法应用于存在的研究算法分析实例上,说明该算法可行性.把该算法应用于本文构造的虚拟企业网络的社团划分上,划分结果与预期相符.     

时变网络下多式联运的最短路径问题研究

在运输过程中,往往不止有一种运输方式,可能同时有多种运输方式交叉,即存在多式联运的方式.同时,运输网络往往具有时变特性,其运输成本和运输时间等会随着时间的变化而变化.将多式联运的运输网络进行了变形,设计了时变网络条件下有到达时间限制多式联运的最短路径算法,并对算法的计算复杂性进行了分析.最后给出一个应用算例.     

含结点等待费用的离散时变最短路径

研究了结点等待费用、弧费用和弧通过时间均为离散时变函数的最短路径问题.基于动态规划原理,给出了一种标号更新算法,可在O(n3M3)时间复杂度内求出所有结点到指定终点的最小费用路径,其中n为网络结点数、M为时间间隔数.     

一种新的大规模网络最短路径的近似算法

平均最短路径长度是复杂网络的一个重要特性,但是对于大规模网络的平均最短路径长度的计算是困难的.在最近的一次对中国教育网的研究中.建立了一个有2 354 934个网页和26 816 209个链接的网络.要想计算该网络的平均最短路径长度,无论是传统的Floyd、Dijkstra算法,还是基于MPI的并行算法,在现有的计算机资源下都难以实现.提出了二级网络的概念,并基于此给出了一种针对中国教育网的新算法,使得在可以接受的时间内完成平均最短路径的近似计算,经试算效果令人满意,说明这种方法对于计算大规模网络的平均最短路径是有效的.     

不完全信息下交通网络最短路径关键边问题

因各种突发事件（交通事故、自然灾害等）造成道路中断的现象普遍存在，车辆在行驶的过程中并不具有道路中断的完全信息，只有行进到中断处时才获得道路中断的信息。本文就不完全信息（道路中断信息）下的变通网络最短路径关键边问题进行研究，首先定义了不完全信息下最短路径关键边的概念．其次给出了求解不完全信息下最短路径关键边的有效算法厦其时间复杂性分析，然后结合城市道路网络给出了实际算例，比较分析了最短路径关键边、最长绕行路关键边和不完全信息下的最短路径关键边问题，指出了不完全信息下的最短路径关键边问题更具有实际意义。     

有向最短哈密尔顿路问题的DNA算法

首次提出了基于分子生物技术的有向最短哈密尔顿路问题的DNA (deoxyribonucleicacid)算法 ,将顶点、权值用DNA片段编码 ,边的方向通过顶点的编码获得。将这些DNA片段放入溶液中进行生化反应 ,通过基本的生物操作及生物酶完成解的产生及最终解的分离。该算法的创新之处在于权值的设计 ,合理有效地用DNA序列表示权值的大小 ,以便于使用常规的生物分离方法进行最优路径的选择。依据分子生物学的实验方法 ,说明了所提算法是有效和可行的。     

资源有限——工期最短的分枝定界算法

本文研究了资源有限－工期最短的优化问题,提出了相应的分枝定界算法。     

不确定情形下通信网络最短路径关键点问题

在通信网络中，因突发事件造成通信路由节点毁坏或者中断的现象时有发生，传输的数据包不得不从中断处沿着最短的替代路径行进到数据包的接收节点，在这种情形下，哪个路由节点中断使得数据包实际行进的总路程最长呢？从通信网络管理的角度来看这是一个非常重要的问题。对该问题．以前的文献都是从确定情形（事先具有节点中断的完全信息）下进行研究的，本文从不确定情形（只有数据包行进到中断节点的邻接点时才获得该节点中断的信息）的角度重新考虑这个问题。本文首先定义了不确定情形下的最短路径关键点概念，给出了计算不确定情形下最短路径关键点的算法及其时间复杂性分析。结合实际通信网络的算例分析，比较了确定情形下最短路径关键点和不确定情形下最短路径关键点问题，指出了不确定情形下最短路径关键点问题更具有实际意义。     

必经点最短路径问题模型及相应遗传算法研究

根据军事运输在路径寻优方面的特殊需求,将必经点最短路径问题分为三类,建立各类问题的数学模型.以分类保序最短路径为例,设计相应的改进遗传算法.该遗传算法构造了独特的适应度函数,使包含较多必经点的染色体能够优先被选择进入下一代种群.通过节点保序算子的引入,保证相关节点之间存在特定的先后次序,并提出一种新的引入必经点变异算子,提高算法的全局搜索能力,加快收敛速度.仿真结果验证了算法的有效性.     

传感器网络中基于链路层服务的最短路由算法

无线传感器网络中,链路通信质量随时空变化很大,并且有5%-15%的非对称链路存在。链路层服务不但可以发现邻居传感器节点,测量和预测邻居节点间的链路通信质量,而且还提供链路数据转发机制来减轻单向链路对其它协议的影响。利用链路层服务,采用分布式最短路由路径建立算法,为每个传感器节点建立了到汇聚节点的最短路由路径,然后从理论上分析了该算法的性能,最后在无线传感器网络模拟器TOSSIM上进行了模拟。实验结果表明,基于链路层服务的最短路由路径建立算法,不仅可以有效地避免建立断路由路径,还可以充分利用单向链路来建立更短的路由路径,有多于15%的传感器节点建立了更短的路由路径,路由跳数也减少了14%-100%。     

介数中心性和平均最短路径长度整合近似算法

基于Brandes算法给出了复杂网络中介数中心性和平均最短路径长度的整合近似算法,通过理论分析和Rocketfuel项目实测数据的实验分析,验证了该整合算法能够快速有效地估计出复杂网络的介数中心性和平均最短路径长度,为进一步的研究工作奠定了基础.     

两种策略下的最短路径并行算法研究与实现

随着智能交通运输系统的研究与应用,对在大规模交通网络上求解最短路径的实时性提出了更高的要求。为了找出适用于实际交通网络的高效最短路径并行算法,首先选取了3种最短路径标号串行算法,以此为基础分别实现了网络复制及网络分割两种策略下求解最短路径的并行算法。最后,从基于G IS的交通规划软件T ransCAD中提取了实际交通路网数据,同时还随机产生了不同规模的稀疏格网,在这些网络中对并行算法的性能进行了测试和分析。结果表明,在8台机器上求解含5 181个节点的实际交通网络中32个源点的最短路径时,基于网络分割的双队列标号修正并行算法的加速比可达到6.32,在其他网络中也表现出较好的加速比及可扩展性。