基于树分解结构的Top-k最短路径查询算法

• 作者: 崇昊旻 陈合
• 来源期刊: 计算机与现代化
• 学科: 工学
• 关键词: Top-k最短路径 树分解 Yen算法
• 年，卷（期）: 2013,（5）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 10-15
• 页数: 6页
• 分类号: TP301.6
• 字数: 6916字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-2475.2013.05.003

摘要

基于树分解原理及性质,本文运用启发式树分解方法将图转换为树结构,并对分解树进行预处理,在这些预存储的索引信息中查询Top-k最短路径.将树分解索引结构应用到Yen算法,通过解决树分解结构上的限制性路径查询,即Top-1最短路径查询,依次循环求解出Top-k最短路径查询.本算法并没有改变Yen算法最坏情况下的时间复杂度,而是通过分解树上的索引信息在分解树上递归查找,快速查找出最短路径.实验结果表明,基于树分解结构的Top-k最短路径查询算法比Yen算法的查询效率高,且存储索引信息在可接受范围内.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	崇昊旻		5	9	2.0	3.0
2	陈合	东南大学计算机科学与工程学院	1	7	1.0	1.0