TD-H2H:时序图上的最短路径查询

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