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

摘要

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