动态图上基于2-HOP COVER的TOP-K最短路径算法

• 作者: 施琴儿
• 来源期刊: 计算机应用与软件
• 学科: 工学
• 关键词: top-k最短路径 动态图 索引集 2-hop cover
• 年，卷（期）: 2019,（4）
• 所属期刊栏目: 算法
• 页码范围: 210-216,229
• 页数: 8页
• 分类号: TP3
• 字数: 7514字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-386x.2019.04.033

摘要

top-k最短路径问题是在给定图中查找两个节点的最短的k条路径的问题.对于大规模的图,这一问题的算法通常分为两个步骤:耗时的一次性预处理和快速的查询应答.但是,很多这样的算法都是针对静态图的.如果图进行了改变,耗时的预处理就要重做.基于静态图中的2-hop cover的top-k最短路径算法,提出一个适用于动态的有向带权图上的top-k最短路径算法,其创新部分是一个更新预处理数据的子程序.该算法只需要修改原始图的很小一部分索引集就可以得到更新后图的索引集,极大地减少了算法的总运行时间.证明了算法的正确性,并分析了算法的时间和空间复杂度.