计算机科学与探索

作者：李新玲, 王一舒, 袁野, 谷香, 王国仁

单位：1. 东北大学 计算机科学与工程学院，沈阳 1101672. 北京理工大学 计算机学院，北京 100081

关键词：时序图,道路网络,树分解,时序索引,最短路径

道路网络上的最短路径查询是一个已经被广泛研究的基本问题。现有的研究通常将道路网络建模为静态图，查询给定节点间距离最短的路径。然而，道路网络具有时序性，将道路网络建模为时序图更符合实际情况。与静态图相比，时序图的规模更大，结构也更为复杂，增加了时序最短路径的查询难度。时序最短路径是指在给定出发时间下，时序图上源节点和目的节点之间旅行时间最短的路径。因此，时序最短路径的结果受给定出发时间影响，为时序最短路径的查询带来了新的挑战，传统的最短路径算法不适用于时序最短路径的查询。将道路网络建模为时序图，并基于树分解提出了TD-H2H索引，利用该索引可以快速准确地实现时序最短路经查询。首先，研究了时序图上的树分解问题，提出时序树分解算法，将图结构转变为树结构。然后，通过树分解快速确定索引结构，提出了高效的索引构建算法，用以构建TD-H2H索引。最后，基于TD-H2H设计了高效的最短路径查询算法TD-OAI。在4个真实公开的数据集上与现有算法进行了实验，结果表明提出算法的查询效率优于现有算法1~2个数量级，证明了提出算法的有效性和效率。

来源：2023年第5期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2023年第5期