基于深度优先搜索的分层网络最短路径算法

摘要：

大规模网络分层后进行数据预处理是其搜索最短路径的加速方法,现有的分层网络数据预处理存在以下问题:随着网络规模越来越大,数据预处理计算量也越来越大;预处理完的数据需要大量储存空间.针对上述问题提出一种基于深度优先搜索的分层网络最短路径搜索算法,该算法将每簇网络抽象成"一个高级节点"组成高级网络,在高级网络上利用深度优先搜索去掉冗余的簇完成数据预处理后,再利用 Dijkstra 算法搜索最短路径.采用该算法在大规模树形分层通信网络上进行最短路径搜索实验,结果表明该算法比基于关键点数据预处理的最短路径算法平均搜索时间稍长,但在数据预处理时间和存储空间上大大降低.

关键词：分层网络、最短路径、数据预处理、深度优先搜索、Dijkstra

所属期刊栏目：49

分类号：TN915.01

在线出版日期：2023-08-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：684-688