时间依赖图下的最小费用路径搜索

该文提出了一种时间依赖图下最小费用路径的高效搜索算法。已有的算法从起点开始向四周扩展以发现到达终点的路径,搜索空间较大,查询耗时。本文从以下两方面减少搜索空间:首先缩小顶点的有效时间区间避免无用的计算,并且在顶点的相应的时间区间的最小费用正确计算出来之后,再计算扩展路径的费用;然后提出一种双向搜索方法,从起点和终点同时出发向四周扩展路径直到两个搜索相遇,从而控制搜索空间在以起点、终点为圆心的两个小圆内。针对路径的时变依赖性设计了双向搜索的停止条件和路径生成方法,理论上证明了方法的正确性。最后,在大规模数据集上测试验证了方法的有效性。