摘要
基于树分解原理及性质,本文运用启发式树分解方法将图转换为树结构,并对分解树进行预处理,在这些预存储的索引信息中查询Top-k最短路径。将树分解索引结构应用到Yen算法,通过解决树分解结构上的限制性路径查询,即Top-1最短路径查询,依次循环求解出Top-k最短路径查询。本算法并没有改变Yen算法最坏情况下的时间复杂度,而是通过分解树上的索引信息在分解树上递归查找,快速查找出最短路径。实验结果表明,基于树分解结构的Top-k最短路径查询算法比Yen算法的查询效率高,且存储索引信息在可接受范围内。
Based on the principle and property of tree decomposition, this paper converts a graph into a tree structure using a heuristic tree decomposition method. It preprocesses the decomposition tree and stores the index for further Top-k shortest path query. Through the solving of constraint path query in tree decomposition（Top-1 shortest path query） , Top-k algorithm computes the first top-k shortest path one by one. It applies tree decomposition method into Yen algorithm. Though Top-k algorithm don＇ t optimize the worst case time complexity, it can recursively compute the shortest path efficiently through using the stored index. Proved by experiment, Top-k algorithm based on tree decomposition is faster than Yen algorithm, and the size of index is acceptable.
出处
《计算机与现代化》
2013年第5期10-15,共6页
Computer and Modernization
基金
国家自然科学基金资助项目(60973023)
