基于树分解结构的Top-k最短路径查询算法 |
| |
引用本文: | 崇昊旻,陈合.基于树分解结构的Top-k最短路径查询算法[J].计算机与现代化,2013(5):10-15. |
| |
作者姓名: | 崇昊旻 陈合 |
| |
作者单位: | 南京地铁建设有限责任公司;东南大学计算机科学与工程学院 |
| |
基金项目: | 国家自然科学基金资助项目(60973023) |
| |
摘 要: | 基于树分解原理及性质,本文运用启发式树分解方法将图转换为树结构,并对分解树进行预处理,在这些预存储的索引信息中查询Top-k最短路径。将树分解索引结构应用到Yen算法,通过解决树分解结构上的限制性路径查询,即Top-1最短路径查询,依次循环求解出Top-k最短路径查询。本算法并没有改变Yen算法最坏情况下的时间复杂度,而是通过分解树上的索引信息在分解树上递归查找,快速查找出最短路径。实验结果表明,基于树分解结构的Top-k最短路径查询算法比Yen算法的查询效率高,且存储索引信息在可接受范围内。
|
关 键 词: | Top-k最短路径 树分解 Yen算法 |
本文献已被 CNKI 等数据库收录! |
|