TD-H2H:时序图上的最短路径查询

道路网络上的最短路径查询是一个已经被广泛研究的基本问题。现有的研究通常将道路网络建模为静态图,查询给定节点间距离最短的路径。然而,道路网络具有时序性,将道路网络建模为时序图更符合实际情况。与静态图相比,时序图的规模更大,结构也更为复杂,增加了时序最短路径的查询难度。时序最短路径是指在给定出发时间下,时序图上源节点和目的节点之间旅行时间最短的路径。因此,时序最短路径的结果受给定出发时间影响,为时序最短路径的查询带来了新的挑战,传统的最短路径算法不适用于时序最短路径的查询。将道路网络建模为时序图,并基于树分解提出了TD-H2H索引,利用该索引可以快速准确地实现时序最短路经查询。首先,研究了时序图上的树分解问题,提出时序树分解算法,将图结构转变为树结构。然后,通过树分解快速确定索引结构,提出了高效的索引构建算法,用以构建TD-H2H索引。最后,基于TD-H2H设计了高效的最短路径查询算法TD-OAI。在4个真实公开的数据集上与现有算法进行了实验,结果表明提出算法的查询效率优于现有算法1～2个数量级,证明了提出算法的有效性和效率。     

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

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

时间依赖的网络中最小时间路径算法

时间依赖的网络与传统网络模型相比更具有现实意义，具有广泛的应用领域，交通网络和通信网络可以抽象为时间依赖的网络模型，当模型中弧的工度是时间依赖的变量，最短路径问题的求解变得非常困难，早期的研究者通过具体的网络实例认识到传统最短路径算法在这种情况下是不正确的，因此给出限制性条件使得传统最短路径算法是有效的。该文从最短路径算法的理论基础入手，从理论上证明了传统最短路径算法，如Dijkstra算法和标号设置算法，在时间依赖的网络上不能有效地求解最短路径问题，并且，在没有任何限制性条件下，给出了时间依赖的网络模型，理论基础，求解最小时间路径的优化条件和SPTDN算法，从理论上证明了SPTDN算法的正确性，算法的实验结果是正确的，最后给出了时间依赖的网络应用实例。     

GIS时变权值网络最短路径算法研究

最短路径分析是GIS网络分析的基础。传统的最短路径算法中,比较经典的算法是Dijkstra算法。由于地理信息系统中的数据具有不确定性、数据量庞大等特点,因此采用传统的Dijkstra算法进行最短路径分析就不适应。为此本文分析了传统网络中的最短路径算法-Dijkstra算法在时变权值网络结构中的局限性,给出了一种适应于时变权值网络的最短路径算法,并且利用改进的邻接表作为存储结构对算法进行了优化。     

稳定的最短路径树及其构造算法

构建最短路径树是动态网络研究的重要问题之一。在动态网络中,当边状态发生变化时会引发最短路径树动态的重新构建,反复地计算不仅消耗大量时间,也会导致最短路径树的频繁变化。提出一种稳定的最短路径树构造算法,使得构造的路径树在动态网络上更稳定,即更新最短路径树所需的操作数更少。该算法通过记录频繁变化的不稳定边并尽可能避免将其加入最短路径树中,从而能够高效地减少边变化带来的操作。实验结果表明,与传统的动态最短路径树算法相比,该算法可以得到更稳定的最短路径树,并且更新时间减少了57.24%,结点更新次数降低了43.6%。     

基于优先队列的时变网络最短路径算法

提出了基于优先队列的时变网络最短路径算法,能克服传统最短路径算法难以对时变网络求解最短路径的缺陷。提出的时间窗选择策略能够在算法求解过程中为节点选择合适的时间窗以降低路径长度,从而求得精确解。进一步地,算法使用了优先队列组织节点集合以提高计算效率。在随机生成的网络数据以及美国道路数据上的实验表明,基于优先队列的时变网络最短路径算法与经典方法相比,不仅能够求得精确解,运算速度也有所提高。     

一种并行模糊神经网络最短路径算法

给出了模糊网络期望最短路径问题的定义,提出一种并行模糊神经网络最短路径（PFNNSP）算法解决模糊网络最短路径问题。PFNNSP算法首先通过模糊模拟对网络中的边权进行估计,接下来脉冲波在神经元之间的并行传播,相互激活搜寻任意一对结点之间的最短路径,最后,算法回溯输出路径表示和路径长度。在随机生成的小规模数据集上的仿真实验表明,PFNNSP算法在边权服从三角模糊分布的网络中执行时间优于Dijkstra算法,在大规模路网信息数据集上的仿真实验表明,PFNNSP算法能够有效求解网络中的最短路径,并且算法在迭代次数和收敛速度上要优于Dijkstra算法和A*搜索算法。     

移动卫星网络中的最短路径算法研究

移动卫星网络的拓扑时变性对其最短路径求解带来新的问题。文章利用提出的移动卫星网络模型,证明了基于传统网络的最短路径算法在移动卫星网络中使用存在局限性,提出了一种适用于移动卫星网络的最短路径求解方法和优化算法,并进行了仿真验证。     

一种SRIO网络负载均衡最短路径路由算法

在串行RapidIO传输过程中,路由选路算法是影响传输性能的重要因素之一。针对串行高速输入-输出(SRIO)网络深度优先搜索分配路径非最优问题,提出一种负载均衡最短路径路由算法。通过广度优先搜索对SRIO网络中的节点进行枚举并建立网络拓扑信息,以路由跳数定义路由的成本,根据改进Floyd-WarShall算法计算并保存交换节点间的K最短路径。给出预期负载的概念和链路上的路由路径数量来定义链路的负载,采用负载均衡算法从K最短路径中进行选路,建立SRIO网络最短路径约束的负载均衡路由。实验结果表明,与深度遍历路由算法、最小跳数算法相比,该算法在网络传输平均跳数、链路平均负载和链路负载均衡方面有更好的表现,能够有效提升SRIO路由网络的稳定性。     

网络最短路径的动态算法

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