面向大图的最短路径查询算法研究

发布时间：2021-09-06 04:14

　　最短路径查询用于返回图中两点之间的最短路径,是图数据管理中的核心操作之一,一直以来都是研究者关注的热点问题。最短路径查询广泛应用在各种道路交通网络、社会网络、生物信息网络中对数据进行分析。随着实际中数据图规模的不断增大和应用领域的不断扩张,最短路径查询处理效率的进一步提升是亟待解决的关键问题。本文针对无向无权图的最短路径查询问题进行研究,具体研究如下:首先,针对实际中数据图比较稀疏且服从幂律分布的特点,提出对原始图进行分割,分别处理的策略。该策略首先从原始图中删除单枝路径来得到一个规模缩减的图。对单枝路径,利用顶点在路径中的相对位置对顶点进行编码,快速计算路径内顶点间的最短距离。对简化图,构建基于简化图的地标标签索引,用于快速求解简化图上顶点对的最短路径。其次,基于单枝路径索引和简化图索引,提出一种高效的最短路径求解方法。该方法的基本思想是:给定两个查询点,如果这两个点同时位于单枝路径或简化图中,则用相应的单枝路径索引或地标标签索引进行快速求解;否则,先查找两个顶点在简化图上的基点,通过计算基点之间的最短路径,以及基点和查询点的最短路径来得到最终的查询回答结果。最后,利用现实当中的数据... 

【文章来源】：燕山大学河北省

【文章页数】：58 页

【学位级别】：硕士

【部分图文】：

无向无权图

第3章基于简化图的索引构建策略17引阶段，需要构建每个顶点的标签索引，没有考虑到顶点之间的相互关系，使得算法存在冗余遍历以及储存了冗余的最短路径信息。图3-1无向无权图G表3-1图G的2-hop标签索引V2-hoplabelv1{(v1,0),(v2,2),(v3,1),(v4,1),(v5,1),(v6,2),(v7,2),(v8,3),(v9,4),(v10,3),(v11,4),(v12,5)}v2{(v2,0),(v3,1),(v5,1),(v6,2)，(v7,3),(v8,2),(v9,3),(v10,1),(v11,2),(v12,4)}v3{(v3,0),(v8,3),(v9,4),(v10,2),(v11,3),(v12,5)}v4{(v4,0),(v5,1),(v7,1),(v8,2),(v9,3),(v10,3),(v11,4),(v12,4)}v5{(v5,0),(v8,1),(v9,2),(v12,3)}v6{(v6,0)}v7{(v7,0)}v8{(v8,0),(v9,1)}v9{(v9,0)}v10{(v10,0),(v11,1)}v11{(v11,0)}v12{(v12,0)}基于以上构建标签索引的问题，本章根据PLL算法构建2-hop标签索引方法的基础上进行完善以及改进，目的是通过减少遍历数据图的次数以及减少冗余的标签索引，从而降低最短路径查询的搜索空间，同时提高最短路径中顶点对的查询处理性能。本章所提出的标签索引构建策略，即ConstructPrune算法。该算法主要思想是针对实际中数据图比较稀疏且服从幂律分布的特点，提出对原始数据图进行分割，分别处理的策略。该策略首先从原始图中删除单枝路径来得到一个规模缩减的图。

第3章基于简化图的索引构建策略19列。定义3.4(简化图)：不包含单枝路径的数据图称为简化图。简化图是一个复杂图，其图的特性是稠密，并且不包含单枝路径。其中在原数据图中删除单枝路径后，基点仍存在于原数据图中。在简化图中，每个顶点的顶点度都会大于等于2。例如图3-3中，是将图3-1中图G中删除所有的单枝路径所得到的，由顶点v1、v2、v3、v4，v5、v6以及彼此相连的边所组成的图是原数据图的简化图。定理3.1：如果原数据图是一个连通图，经过删除某个或所有的单枝路径(不包含基点)后的简化图依然也是一个连通图。证明：在单枝路径中基点的顶点度至少为3，其中的至少1个是单枝路径上的点，去掉单枝路径并没有对非单枝路径上的点和边做任何改动，不影响连通性。因此，若原数据图为一个连通图，简化图也是一个连通图。证毕。定义3.5(简化图标签索引)：在简化图中，依次对各个顶点进行广度优先遍历，根据2-hop标签索引来构建最短路径标签索引，该标签索引为L(v)，该索引包含若干个二元组(u,)，其中u表示为数据图中另一结点，表示v到u的最短距离。定义3.6(顶点优先级)：假设有一数据图G，其中在一个最短路径生成树G-Tree中，将树结点的子树宽度与在图G中的顶点度的大小相乘作为顶点的优先级顺序，优先级越高的顶点，在算法中其处理顺序越优先。例如图3-2，是对图3-1所求得的最短路径树，按优先级数值降序，各顶点的排列为：v2，v5，v3，v10，v6，v8，v4，v11，v1，v9，v7，v12。图3-2图G的最短路径树

【参考文献】：
期刊论文
[1]路网环境下访问序列受限的多标签路线查询算法[J]. 张金增,文洁,孟小峰.  计算机学报. 2012(11)



本文编号：3386725