大规模图数据边受限制的最短距离查询算法

摘要

计算两点之间的最短距离是标记图的基本操作之一.对于大图,根据路标节点估算两点之间最短距离的方法来提高查询效率.现有的路标节点选择策略不能在中心性和计算量小两方面同时满足,路标节点存储到其他节点的距离信息,存储量仍然很大.对于大规模有向图来说,路标节点选取策略保证中心性的同时减少了计算量,使用了DBSCAN聚类思想将节点划分成不同的类,选择具有联通性的向前和向后核心节点作为向前和向后路标节点;存储类内路标节点与普通节点之间的距离信息以及类间路标节点之间的距离信息来减少存储量;源节点通过向后路标节点和向前路标节点到达目标节点,采用上界和下界的最小均值作为估计值.理论证明算法策略在时间复杂度和空间复杂度方面与传统方法相比降低了.实验证明对于大图在平均相对误差方面与传统方法误差数量级相同.