时间依赖代价函数下的最优路径查询问题研究

• 作者: 李建中 杨雅君 高宏
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 时间依赖图 代价函数 最优路径
• 年，卷（期）: 2012,（11）
• 所属期刊栏目: 研究论文
• 页码范围: 2247-2264
• 分类号: TP311
• 字数: 19660字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2012.02247

摘要

作者研究了时间依赖图下,具有时间限制的费用代价最优路径的查询问题.目前有关时间依赖图上的最短路径查询的研究工作解决的是最短旅行时间问题(TDSP),这些工作都利用了以下性质:到达某个顶点的最早时刻可以通过到达其邻居的最早时刻计算得出.然而,在计算具有时间限制的费用代价最优路径时,该性质并不成立.因此,目前解决TDSP问题的方法均不能解决文中面对的问题.对此作者提出一个新的算法用于计算时间依赖图模型上的满足时间限制的费用代价最优路径.该算法适用于有向图和无向图.作者证明了算法的时间复杂度和空间复杂度分别为O(kn logn+mk2logk)和O((n+m)k).最后,作者通过真实数据集上的实验,验证了该算法的有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李建中	哈尔滨工业大学计算机科学与技术学院	237	6003	33.0	72.0
2	高宏	哈尔滨工业大学计算机科学与技术学院	109	1574	18.0	36.0
3	杨雅君	哈尔滨工业大学计算机科学与技术学院	3	18	3.0	3.0