软件学报

作者：马慧,汤庸,梁瑞仕

单位：马慧，电子科技大学 中山学院 计算机学院, 广东 中山 52840011,汤庸，华南师范大学 计算机学院, 广东 广州 51063102,梁瑞仕，电子科技大学 中山学院 计算机学院, 广东 中山 52840003

关键词：时间信息图;最小时态路径;费用限制;图索引;hub-labelling

基金：国家自然科学基金（U1811263，61772211）；广东省高等学校优秀青年教师项目（YQ2015241，YQ2015242）；中山市科技计划（2015B2307）

私人交通网络下的最短路径查询主要考虑路径长度、行驶时间等因素，而公共交通网络下的路径查询需要考虑路径上相邻的边的时间顺序约束以及路径的费用.研究了公共交通网络下3种查询：给定起点、终点、时间区间和费用上限，查找在时间区间内不超过费用上限的最早到达路径、最晚出发路径和最短耗时路径.首先给出一种Dijkstra变种算法Dijk-CCMTP，在此基础上给出3类查询的查询算法.然后提出一种高效的索引结构ACCTL（approximate cost constrained time labelling）.ACCTL采用Dijk-CCMTP对图中的每个顶点预先计算部分从该顶点出发的和到达该顶点的基本路径.对于任意从起点s到终点d的查询，可以采用类似数据库表连接的方式从ACCTL中连接从a出发的和到达d的路径生成近似解，避免遍历原图搜索路径.ACCTL建立索引的时间复杂度是O（|V|·△max·|E|·（log|E|+△max）），其中，|V|表示顶点数，|E|表示边数，△max表示顶点的最大度数.实验验证ACCTL索引支持的查询速度比Dijkstra的变种算法的查询速度快2~3个数量级，并分析了影响建立索引时间和空间大小的因素.

来源：2019年第11期

《软件学报》期刊编辑部

查看软件学报杂志2019年第11期