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

TOP-K SHORTEST-PATH ALGORITHM BASED ON 2-HOP COVER ON DYNAMIC GRAPH

作　　者：施琴儿 Shi Qiner(Fudan University and Zhongan Technology Blockchain and Information Security Joint Lab, School of Computer Science,Fudan University, Shanghai 200433, China;The Shanghai Blockchain Institute of Engineering and Technology, Shanghai 200433, China)

机构地区：[1]复旦大学计算机科学技术学院复旦-众安区块链与信息安全联合实验室,上海200433 [2]上海市区块链工程技术中心,上海200433

出　　处：《计算机应用与软件》2019年第4期210-216,229,共8页Computer Applications and Software

基　　金：国家自然科学基金项目(61672166);上海市领军人才计划项目(2016-021);2016年上海市优秀学术带头人项目(16XD1400200);上海市基础研究科技创新行动计划项目(16JC1402700)

摘　　要：top-k最短路径问题是在给定图中查找两个节点的最短的k条路径的问题。对于大规模的图,这一问题的算法通常分为两个步骤:耗时的一次性预处理和快速的查询应答。但是,很多这样的算法都是针对静态图的。如果图进行了改变,耗时的预处理就要重做。基于静态图中的2-hop cover的top-k最短路径算法,提出一个适用于动态的有向带权图上的top-k最短路径算法,其创新部分是一个更新预处理数据的子程序。该算法只需要修改原始图的很小一部分索引集就可以得到更新后图的索引集,极大地减少了算法的总运行时间。证明了算法的正确性,并分析了算法的时间和空间复杂度。Top-k shortest-path problem can be described as finding the shortest K paths of two nodes in a given graph. The algorithm for this problem on large-scale graphs often follows 2 steps: me-consurning one-time pre-pTocessing and fast query-answering. However, many algorithms are designed for static graphs. If the graphs are changed, the costly pre-processing has to be redone. Based on the 2-hop cover top-k shortest path algorithm in the static graph , we proposed topshortest-path algorithm for dynamic directed weighted graphs. The novel part was a subroutine for updating the pre-processing data. With our algorithm, the index set of the updated graph were obtained by only changing a small fraction of the index set of the original graph , which greatly reduced the overall running time. We prove the correctness of our algorithm , and analyze its time and space complexity.

关 键 词：top-k最短路径 动态图 索引集 2-hop COVER 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]