查询结果:   施琴儿.动态图上基于2-HOP COVER的TOP-K最短路径算法[J].计算机应用与软件,2019,36(4):210 - 216,229.
中文标题
动态图上基于2-HOP COVER的TOP-K最短路径算法
发表栏目
算法
摘要点击数
380
英文标题
TOP-K SHORTEST-PATH ALGORITHM BASED ON 2-HOP COVER ON DYNAMIC GRAPH
作 者
施琴儿 Shi Qiner
作者单位
复旦大学计算机科学技术学院复旦-众安区块链与信息安全联合实验室 上海 200433 上海市区块链工程技术中心 上海 200433    
英文单位
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    
关键词
top-k最短路径 动态图 索引集 2-hop cover
Keywords
Top-k shortest-path Dynamic graph Index set 2-hop cover
基金项目
国家自然科学基金项目(61672166);上海市领军人才计划项目(2016-021);2016年上海市优秀学术带头人项目(16XD1400200);上海市基础研究科技创新行动计划项目(16JC1402700)
作者资料
施琴儿,硕士生,主研领域:算法,计算复杂性。 。
文章摘要
top-k最短路径问题是在给定图中查找两个节点的最短的k条路径的问题。对于大规模的图,这一问题的算法通常分为两个步骤:耗时的一次性预处理和快速的查询应答。但是,很多这样的算法都是针对静态图的。如果图进行了改变,耗时的预处理就要重做。基于静态图中的2-hop cover的top-k最短路径算法,提出一个适用于动态的有向带权图上的top-k最短路径算法,其创新部分是一个更新预处理数据的子程序。该算法只需要修改原始图的很小一部分索引集就可以得到更新后图的索引集,极大地减少了算法的总运行时间。证明了算法的正确性,并分析了算法的时间和空间复杂度。
Abstract
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-consuming one-time pre-processing 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 top-k shortest-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.
下载PDF全文   

根据该篇关键词查找到本刊已发表相关论文供参考
序号
文  章  标  题
作者1
发表栏目
页码
摘要
1
动态图上基于2-HOP COVER的TOP-K最短路径算法
施琴儿
算法
2019
4
210
[摘要]