图，作为一种通用的数据结构，用于表示各种对象之间的复杂关联关系.图上最短路径计算作为基础功能函数，有着广泛的应用.例如，路径规划[1]、城市交通路线优化[2]、社交网络分析[3]等.现有的最短路径算法主要聚焦在普通图，然而，真实场景中，图中常常附有时态信息，2个顶点之间的边关联的事件在某一时间点发生并持续一段时间结束，此种类型的图称之为时态图.

图1列举了时态图应用在公交时刻图的例子.图中顶点表示公交站点，时态边上附带有时态区间，表示公交车从一个站点到另一个站点的出发时间和到达时间.例如，一班89路公交车早上7∶00从浙大玉泉校区始发站出发，7∶15到达古荡站点，停靠站1 min，7∶16出发，经府苑新村，蒋村公交站，最终在8∶15到达三墩终点站.此例中，时态图最短路径查询有助于乘客查询指定时态区间内的2个站点间的最短路径，从而为乘客智能推荐公交线路.给定时态图GT=(VT,ET)，查询源点u，查询目的点v，时态区间I，本文研究的时态图最短路径旨在图GT中查询u到v在时态区间I内的最短时态路径距离.时态图GT中的边除了关联时态区间外，还附加有权重值，在交通路网中可以表示距离；在公交/地铁/航班时刻图中可以表示费用；在社交网络中可以表示用户之间的亲密度.与已有的最短路径查询问题相比，最短时态路径更具挑战性.

首先，计算最短时态路径时需要考虑边与边的时序流转特性，否则如果运用现有的普通图最短路径计算方法，会产生错误的结果.例如，图1中，假设边上权值均为1，乘客想要查询云栖小镇站到三墩站在时态区间[7∶00,9∶00]的时态最短路径距离.如果不考虑边之间的时序流转特性，则计算得到的结果为3，对应的最短时态路径为(云栖小镇，府苑新村，蒋村公交站，三墩)或(云栖小镇，府苑新村，董家村，三墩).实际这2条路径均不能到达三墩站.对于第一条路径，121路云栖小镇到府苑新村时间为8∶20，其不能赶上7∶32从府苑新村出发经由蒋村公交站最终到达三墩站的89路公交车.对于第二条路径，121路换乘70路8∶50到董家村，同样赶不上8∶26到三墩站的12专线.鉴于此，时态最短路径计算过程中需要考虑时序流转特性，此例计算得到的结果应为4，对应的最短时态路径应为(云栖小镇，翠苑，大关，董家村，三墩).

其次，最短时态路径并不满足子路径最优性质,即顶点u到顶点v的最短时态路径的子路径并不一定是最短时态路径.上例中，子路径(云栖小镇，翠苑，大关，董家村)并不是时态区间[7∶00,9∶00]内的最短时态路径，云栖小镇到董家村在时态区间[7∶00,9∶00]内最短时态路径应为(云栖小镇，府苑新村，董家村).这导致计算时态最短路径时更复杂，因为需要考虑所有的路径.

目前，已有一些工作[4-5]研究时态图最短路径查询.然而，它们一般假设输入时态图为FIFO(first-in-first-out)时间依赖图，FIFO时间依赖图是指图输入边上的时间间隔表示为出发时间的函数，这个函数具有FIFO属性，即若出发时间早，则到达时间也早.这类问题具有一定的特殊性，实际交通工具出行时刻图或社交接触网络不一定是FIFO时间依赖图.与本文工作最相关的是文献[6-7]提出的one-pass算法，其将时态图转化为普通图，而后在普通图上采用广度优先搜索和Dijkstra算法计算最短时态路径，但其在较大规模数据集上效率较低.鉴于此，本文研究时态图最短路径问题并提出了基于层次索引的计算方法，其主要包含预处理和在线查询2个阶段.预处理阶段本文提出了一种无损压缩方法和层次索引CTG-tree(compressed transformed graph tree).首先将时态图转化为普通图，对普通图进行压缩以减小规模，将时态图上最短路径计算转化为在压缩结果图上执行.而后在压缩结果图上构建CTG-tree，它将G-tree[8]的思想扩展到压缩有向图上，首先采用Metis划分将压缩图层次划分为若干个子图，得到每个子图的入边界点与出边界点集合.CTG-tree为每个叶子节点对应子图计算其内部顶点与出边界点的最短路径、入边界点到子图内顶点的最短路径和出边界点到入边界点的最短路径；非叶节点计算其对应子图入边界点到其所有孩子节点对应子图的入边界点之间的最短路径距离、所有孩子节点对应子图的出边界点到当前非叶节点对应子图的出边界点之间的最短路径距离、以及所有孩子节点对应子图的出边界点到所有孩子节点对应子图的入边界点之间的最短路径距离作为索引.查询阶段本文基于层次索引CTG-tree设计了高效的最短路径查询算法.概括而言，本文的主要贡献有4个方面:

1) 提出了一种基于层次索引的两阶段(预处理阶段和查询阶段)方法以高效地计算时态图最短路径;

2) 提出了一种无损压缩方法和层次索引CTG-tree，将时态图上最短路径计算结果转化为在压缩结果图上执行.CTG-tree将G-tree的思想扩展到压缩有向图上；无损压缩在减小图处理规模的同时还保证了压缩结果图上最短路径计算的准确性；

3) 提出了基于CTG-tree索引的查询算法以高效地支持时态图最短路径查询;

4) 基于4个真实的时态图数据集，进行了充分的实验评估，验证了本文提出的基于层次索引的最短时态路径算法的高效性.

1 相关工作

本节分别概述已有的普通图和时态图最短路径查询算法.

1.1 普通图最短路径查询算法

综述文献[1,9]将普通图最短路径问题划分为点到点的最短路径计算、单源最短路径计算和所有点对最短路径计算3类问题.点到点的最短路径计算指定点对之间的最短路径；单源最短路径计算一个点到其他所有点的最短路径距离；所有点对最短路径计算图中所有点对之间的最短路径距离,其可通过单源最短路径计算得到.已有的最短路径查询算法大多是基于经典的Dijkstra方法，文献[10]从理论角度分析了单源最短路径基于堆的优先级队列算法的时间复杂度是O(m log n)；采用斐波那契堆的时间复杂度是O(m+n log n).文献[11]提出了基于Dijkstra的变体方法Sky-Dijk.为了缩小搜索空间，双向搜索算法[12-13]被提出.由于Dijkstra方法及其变体算法在大图上运行时间较长，因此研究人员提出了一系列基于索引的最短路径算法[8,14-20]以提高查询效率.例如，文献[14]提出了基于标志点(landmark)的算法，其预先选择一些顶点作为标志点；并且预先计算图中每个顶点与标志点之间的最短路径距离.图中任意一对顶点之间的最短路径距离上下界可以运用预先计算好的距离计算得到；文献[15]提出了基于剪枝的标志点标签，通过剪枝的广度优先搜索预计算所有顶点的距离标签，通过距离标签计算任意点对的最短路径距离.文献[16]提出了收缩层级结构；将图中的顶点或者边按照重要度排序，再根据排序的结果迭代，最终生成层级嵌套索引.文献[8]提出了G-tree索引，其首先将路网层次划分为若干个子图，再计算每个子图内的顶点与边界点之间的距离，子图间的边界点与边界点之间的距离作为索引，基于G-tree索引提高查询效率.基于索引的最短路径算法关键在于平衡查询时间、索引时间、索引空间；为了减小索引空间，文献[17-18]还提出了索引压缩方法.

针对动态图，文献[19]提出了DCHvcs,其扩展收缩层级结构以支持动态图.文献[20]在收缩层级最短路径索引的基础上，构建辅助的图结构以及权重传播机制来处理流式和批量的路网权重更新.文献[21]提出了CRP方法以支持最短路径索引的动态更新.针对大规模输入图，文献[22]基于分布式流处理系统Yahoo S4，提出了2种异步通信算法以支持动态最短路径；文献[23]探索了边受限的最短路径查询问题.此外，一些研究人员还致力于近似最短路径计算方法研究[24-25].文献[24]提出了距离Oracle数据结构，对于(2k-1)-近似能在O(k)的时间内给出任意节点对之间的近似最短路径.文献[25]将大图近似为一个规模相对小的spanner稀疏子图，而后在子图上做近似最短路径计算.概括而言，上述算法均针对普通图，并没有考虑边上附带的时态信息，因此不能直接有效地应用在时态图上.

1.2 时态图最短路径查询算法

综述文献[1]总结了时间依赖图的最短路径查询算法.时间依赖图中边延迟函数计算一条边中源点到目的点所需时间，时间函数可分为离散或连续的.

文献[2,6-7,26]针对离散时间下的最短路径进行了研究.文献[2]提出了TD-G-tree索引以支持时间依赖路网上最短路径查询，但是其与本文研究问题不同，并没有考虑路径内边之间的时序关系.文献[26]提出了时间表标签(time table labelling, TTL)索引；文献[6-7,27]提出将时态图转化为普通图，基于此，文献[27]研究了时间依赖的可达性查询，其提出了TopChain标签索引方法以解决时态图上的可达性查询、最早到达时间查询、最小间隔时间查询.与其研究的问题不同，本文旨在解决时态图上的最短路径查询.文献[6-7]在转化的普通图上采用广度优先搜索和Dijkstra算法计算2点之间给定时间段内的最短路径.本文基于上述工作，将时态图转化为普通图后，利用压缩以及层次索引技术高效支持最短时态路径查询.

文献[3-5]针对连续时间下的最短路径进行了研究.文献[4]提出了基于Dijkstra算法返回耗时最少旅行时间的最优出发时间；文献[3]首先定位给定时态区间段内子图，而后在子图中采用Dijkstra计算最短路径.文献[5]在文献[4]的基础上，研究的时态图中边除了边延迟函数外，还添加了权重代价函数，利用这2种函数的结构属性设计最短路径算法.这类工作通常假设输入时态图为FIFO时间依赖图，输入边上时间间隔表示为出发时间的函数，出发时间早，则到达时间也早，这类问题具有一定的特殊性.而在我们的问题中，输入边有出发时间和到达时间，输入图(例如交通工具出行时刻图或者社交接触网络)不一定是FIFO时间依赖图，这导致计算时态最短路径时更复杂，最短路径计算不满足最优子结构特征，因为需要考虑边与边的时序流转特性，计算难度更高.

2 问题定义

本节主要介绍时态图、时态路径相关概念，最后给出问题定义.

定义1. 时态图[6].本文定义的时态图是复杂有向图，表示为GT=(VT,ET)，其中VT表示顶点集合；ET⊆VT×VT是有向边的集合，具体地，连接顶点u∈VT到v∈VT/{u}的有向边ei∈ET表示为一个五元组(u,v,wi,sti,ati)，表示u与v之间的事件发生起始时间是sti，终止时间是ati.时间间隔是I=(sti,ati)，持续时间为|I|=ati-sti，wi表示每条时态边ei的非负权重值，表示耗费时间或者路程等.

不同于简单图，时态图中2个顶点之间可能有多条时态边.与普通图路径定义不同，时态图中时态路径的定义如下：

定义2. 时态路径.从顶点u到v的时态路径p，表示为p(u,v)=u,e1,v1,…,vm-1,em,v,其中u,v1,v2,…,vm-1,v表示顶点序列，e1,e2,…,em-1,em表示时态边序列，e1=(u,v1,w1,st1,at1)，ei=(vi-1,vi,wi,sti,ati)(1<i<m)，em=(vm-1,v,wm,stm,atm)，使得对于任意的1≤i≤m，ati≤sti+1.令Sp=st1表示p的开始时间，Ep=atm表示p的到达时间，Dp=atm-st1表示p的时间间隔.表示p的路径权重.

给定时态图GT，源点s，目的点s′，时间间隔I=[ts,ta]，定义函数TPSetG(s,s′,I=[ts,ta])为从顶点s到顶点s′的所有满足Sp≥ts,Ep≤ta的GT中的时态路径p构成的集合.基于此给出定义3.

定义3. 最短时态路径查询.给定时态图GT，源点s，目的点s′，时间间隔I=[ts,ta]，最短时态路径查询返回s在时间间隔I内到达s′的时态路径权重最小值

本文定义的最短时态路径查询问题可用于城市交通路线查询与推荐.例如，给定图1所示的公交时刻图GT，源点s设置为浙大玉泉校区站，目的点s′设置为三墩站，时态区间I=[7∶00,9∶00]，则根据定义1，定义2和TPSetG函数定义得到TPSetG(浙大玉泉校区站,三墩站,[7∶00,9∶00])={浙大玉泉校区,(浙大玉泉校区，翠苑，1，7∶30，7∶45)，翠苑,(翠苑，大关，1，7∶46，8∶00)，大关,(大关，董家村，1，8∶01，8∶25)，董家村，(董家村，三墩，1，8∶26，9∶00)，三墩,浙大玉泉校区,(浙大玉泉校区，古荡，1，7∶00，7∶15)，古荡,(古荡，府苑新村，1，7∶16，7∶31)，府苑新村,(府苑新村，蒋村公交站，1，7∶32，7∶50)，蒋村公交站，(蒋村公交站，三墩，1，7∶51，8∶15)，三墩}.对应2条线路：分别是79路—121专线；89路.根据定义3，浙大玉泉校区站到三墩站的最短时态路径距离为4.

3 CTG-Tree构建

本文提出了基于层次索引的计算方法，主要包含预处理和在线查询2个阶段.本节详细阐述预处理阶段提出的无损压缩方法和层次索引CTG-tree.

3.1 基于转化图的无损压缩

在时态图上计算最短时态路径的直接方法是进行广度优先搜索或者深度优先搜索，但是由于时态最短路径不满足子路径最优性质，因此在搜索过程中需要保存计算遍历到的所有路径，此种方法效率较低.因此本文的主要思想是先将时态图转化为普通图，而后进行压缩，再利用索引加速查询.具体地，本文利用文献[6]提出的方法将时态图GT=(VT,ET)转化为普通图G=(V,E)，其中转化图G已被证明为有向无环图[6]，具体的转化过程如下.

每个顶点u∈VT转化为V中的2个集合Vin(u)和Vout(u)，Vin(u)={u,ati|1≤i≤h}，Vout(u)={u,stj|1≤j≤m}，其中ati是u入边中到达u的不同时间实例，stj是u出边中从u出发的不同时间实例.h和m分别表示不同的到达时间实例数目和出发时间实例数目.边转化过程涉及到3步.1)每条边ei=(u,v,wi,st,at)转化为u,st∈Vout(u)到顶点v,at∈Vin(v)的边，边的权重为wi.2)令Vin(v)={v,at1,v,at2,…,v,ath},对于1≤i≤h-1,创建从v,ati到v,ati+1的边，边的权重为0.同样的，对于Vout(v)集合，采用相同的方式创建边.3)对于顶点v,atin∈Vin(v)，按照Vin(v)中顶点的逆序顺序，创建从v,atin到v,stout∈Vout(v)的边，边的权重为0.其中stout=min{st′|v,st′∈Vout(v),st′≥atin}，并且没有v,atin∈Vin(v)到v,stout的边创建.

图2给出了转化图示例.图2(a)为输入的时态图GT，边上附带的值为边事件的出发时间，假设边权重、边时态区间间隔均为1.图2(b)为转化后的有向图G.以图2(a)中的顶点v3为例，v3转化为Vin(v3)={v3,3,v3,5}，Vout(v3)={v3,6,v3,7}.以图2(a)中的边(v3,v4,6,7)为例，其转化为v3,6∈Vout(v3)到v4,7∈Vin(v4)的边.对于Vin(v3)，创建v3,3到v3,5的边.对于Vout(v3)，创建v3,6到v3,7的边.此外，需要创建v3,5∈Vin(v3)到v3,6∈Vout(v3)的边.

转化图的规模通常为时态图的几十倍甚至上百倍，如果根据文献[6-7]，直接在转化图上采用广度优先搜索或Dijkstra算法计算最短路径，则搜索空间较大，耗费时间.可以观察到，转化图规模庞大的原因是时态图中的一个顶点拆分为Vin，Vout集合中的多个顶点.Vin，Vout集合中的顶点连接的边权重均为0，并且一些顶点对具有相同的邻居，鉴于此，本文提出了一种无损压缩规则：原始时态图中的顶点v转化的Vin或Vout集合中的顶点v,t1与v,t2,t1<t2,如果其满足v,t1与v,t2的入度邻居和出度邻居除v,t1与v,t2外相同，则顶点v,t1与v,t2压缩为v,T,T={t1，t2}.

图2(c)给出了图2(b)按照上述无损压缩规则得到的压缩图G′.转化图G中的v4,7∈Vin(v4)与v4,8∈Vout(v4)压缩为v4,{7，8}∈G′；G中的v3,6∈Vout(v3)与v3,7∈Vout(v3)压缩为v3,{6，7}∈G′;G中的v5,8∈Vin(v5)与v5,9∈Vout(v5)压缩为v5,{8，9}∈G′.

具体的压缩算法伪码如算法1所示.其中，Nin(v,t)={u,t′|(u,t′,v,t)∈E}和Nout(v,t)={m,t′|(v,t,m,t′)∈E}分别表示转化图G中顶点v,t的入度邻居和出度邻居集合.算法1首先遍历转化图G中的Vin(v)或Vout(v)集合中的所有顶点(行①)，如果集合中的任意2个顶点v,t1和v,t2满足上述无损压缩规则，则v,t1与v,t2合并为v,{t1,t2}(行②～④)；如此得到最终的无损压缩图G′.

算法1. 基于转化图的无损压缩算法.

输入：基于时态图GT=(VT,ET)的转化图G=(V,E)；

输出：无损压缩图G′=(V′,E′).

① for each v∈GT,v,t1,v,t2∈Vin(v)∪Vout(v)

② if Nin(v,t1)/v,t2=Nin(v,t2)/

v,t1且Nout(v,t1)/v,t2=

Nout(v,t2)/v,t1

③ v,t1与v,t2合并为v,{t1,t2}；

/*根据规则进行压缩*/

④ end if

⑤ end for

⑥ 输出无损压缩图G′=(V′,E′).

明显地，算法1的时间复杂度为|Vout(v)|)2(|Nin(v,t)|+|Nout(v,t)|),空间复杂度为O(|V|+|E|).

3.2 CTG-tree索引

基于上述无损压缩图，构建层次索引CTG-tree.分为2个步骤：

1)
图层次划分.由于Metis划分保证每次划分的子图顶点数目相近，交叉边数目较少，因此本文采用Metis层次划分，首先将无损压缩图G′划分为若干子图G1，G2，…，Gl(l≥2)，而后在每个子图Gi(1≤i≤l)上进行迭代划分直至划分的子图顶点数目不超过指定的阈值θ；最终形成平衡树CTG-tree.G′为CTG-tree的根节点，第i次迭代划分的子图为CTG-tree第i层节点，叶子节点对应子图的顶点数目不超过阈值θ. Metis划分属于边划分方法，每次迭代划分的子图之间没有交集(例G1∪G2∪…∪Gl=G′,G1∩G2∩…∩Gl=∅)，但是会产生跨子图的交叉边e(u,v),u∈Gi,v∈Gj.基于此，本文将子图内顶点分为3类：入边界点、出边界点和内部顶点.令Gi.Bi,Gi.Bo,Gi.VI分别表示子图Gi=(Vi,Ei)的入边界点、出边界点和内部顶点的集合，则

① Vi=Gi.Bi∪Gi.Bo∪Gi.VI；

② ∀u∈Gi.Bo，至少存在一条跨分区的交叉边e=(u,m),u与m隶属不同子图，即m∉Gi；

③ ∀v∈Gi.Bi，至少存在一条跨分区的交叉边e=(s,v),s与v隶属不同子图，即s∉Gi；

④ ∀v′∈Gi.VI，v′的所有入度邻居.出度邻居都隶属子图Gi，即Nin(v′)⊆Vi,Nout(v′)⊆Vi；

在图划分步骤中，每个子图记录相应的入边界点，出边界点.

2) 最短路径距离矩阵计算.对于CTG-tree中的叶子节点对应的子图Gi，需要计算3个最短路径距离矩阵，即游出距离矩阵Gi.Do、游入距离矩阵Gi.Di和边界点距离矩阵Gi.Db. Gi.Do保存Gi中所有顶点到每个出边界点的最短路径距离；Gi.Di保存Gi中每个入边界点到所有顶点的最短路径距离；Gi.Db保存Gi中所有出边界点到入边界点的最短路径距离.对于CTG-tree中的非叶子节点对应的子图Gj，需要计算出边界点游入距离矩阵Gj.DBi、入边界点游入距离矩阵Gj.DIi和边界点游出距离矩阵Gj.DBo；Gj.DBi保存Gj所有孩子节点对应子图的出边界点到Gj所有孩子节点对应子图的入边界点之间的最短路径距离；Gj.DIi保存Gj入边界点到Gj所有孩子节点对应子图的入边界点之间的最短路径距离；Gj.DBo保存Gj所有孩子节点对应子图的出边界点到Gj出边界点之间的最短路径距离.

具体的CTG-tree索引构建算法伪码如算法2所示.

算法2. CTG-tree索引构建算法.

输入：无损压缩图G′=(V′,E′)，Metis每层划分的子图数l，叶子子图顶点数阈值θ；

输出：CTG-tree索引.

① CTG-tree←Metis(G′,l,θ)；

② for each layer(自底向上) of CTG-tree

③ if leaf node← /*叶子节点层计算*/

④ Gi.Do,Gi.Di,Gi.Db←Dijkstra(G′)；

⑤ else /*非叶子节点层计算*/

⑥ Gj.DBi←Dijkstra(G′);Gj.DIi←

Dijkstra(G′);

Gj.DBo←Dijkstra(G′)；

⑦ end if

⑧ end for

⑨ 输出CTG-tree索引.

算法2首先在给定的无损压缩图G′上进行Metis层次划分，得到CTG-tree(行①)，需要说明的是，无损压缩图中，边权重为0会影响Metis划分过程，因此需要适当增权处理.

接着，对CTG-tree自底向上遍历计算索引矩阵(行②).对于叶子节点，利用Dijkstra算法在图G′上计算叶子节点对应子图Gi的游出距离矩阵Gi.Do、游入距离矩阵Gi.Di和边界点距离矩阵Gi.Db(行③～④).对于非叶节点，利用Dijkstra算法在图G′上计算对应子图Gj的出边界点游入距离矩阵Gj.DBi、边界点游出距离矩阵Gj.DBo和入边界点游入距离矩阵Gj.DIi，值得注意的是，此过程可以利用顶点拓扑序加速计算过程，由于转化图是有向无环图，压缩图即为有向无环图，因此在运用Dijkstra算法前，可先计算顶点拓扑序，若在计算顶点u到v的最短路径时，u的拓扑序大于v的拓扑序，则顶点u到v的最短路径一定为∞.

图3所示为图2(c)的CTG-tree索引构建过程.图3(a)表示Metis划分过程，其中l=2,θ=5.首先，G′被划分为G1和G2,接下来G1被划分为G3和G4；G2被划分为G5和G6；因为|V3|=|V6|=4<θ,|V4|=|V5|=5≤θ，所以Metis终止划分.构建的CTG-tree得到的每个子图的入边界点、出边界点如图3(b)所示.例如G4.Bi={v1,4,v3,3,v4,6}；G4.Bo={v3,{5,6},v4,{7,8}}；G2.Bi={v3,7,v6,9}；G2.Bo=∅.

随后，计算CTG-tree中的叶子节点对应子图G3，G4，G5和G6的游出距离矩阵Gi.Do、游入距离矩阵Gi.Di和边界点距离矩阵Gi.Db.

例如，对于子图G4，G4.Do计算G4所有点v1,4,v3,3,v4,6,v3,{5,6},v4,{7,8}到所有出边界点v3,{5,6},v4,{7,8}的最短路径距离；G4.Di计算G4所有入边界点v1,4,v3,3,v4,6到所有点v1,4,v3,3,v4,6,v3,{5,6},v4,{7,8}的最短路径距离；G4.Db计算G4所有出边界点v3,{5,6},v4,{7,8}到入边界点v1,4,v3,3,v4,6的最短路径距离.

而后，自底向上计算非叶节点对应子图G1，G2和G0的出边界点游入距离矩阵Gj.DBi、入边界点游入距离矩阵Gj.DIi和边界点游出距离矩阵Gj.DBo.

例如，对于子图G1，G1.DBi计算G3和G4的所有出边界点v1,2,v2,{3,5},v3,{5,6},v4,{7,8}到G3和G4的所有入边界点v1,4,v3,3,v4,6最短路径距离；G1.DBo计算G3和G4的所有出边界点v1,2,v2,{3,5},v3,{5,6},v4,{7,8}到G1的出边界点v3,{5,6},v4,{7,8}之间的最短路径距离.对于子图G2，G2.DIi计算G2入边界点v3,7,v6,9到G5和G6的所有入边界点v3,7,v6,9,v5,11,v7,{11，13}之间的最短路径距离；最终CTG-tree中每个节点保存的距离矩阵索引如图4所示.

CTG-tree索引保存3部分信息：CTG-tree节点、边界点以及距离矩阵.CTG-tree叶子节点对应子图的顶点数目不超过阈值θ,每层节点数为l，所以CTG-tree高度为logl(|V|/θ)+1，CTG-tree节点总数为l|V|/(l-1)θ.CTG-tree边界点总数为

CTG-tree距离矩阵大小为

|Gj.Db|).

所以CTG-tree索引空间复杂度为

|Gj.Do|+|Gj.Db|)).

4 基于CTG-tree索引的最短路径计算方法

本节详细阐述在线查询阶段提出的基于层次索引CTG-tree的最短路径计算方法.

给定时态图GT，源点s，目的点s′，时间间隔I=[ts,ta]，顶点s在时间间隔I内到达s′的最短时态路径转化为在压缩图G′=(V′，E′)计算s,Ts到s′,Te的最短路径d(s,Ts,其中，Ts包含Vout(s)中大于或等于ts的最小时间值；Te包含Vin(s′)中小于或等于ta的最大时间值；函数PSetG′(s,Ts,s′,Te)为G′中从顶点s,Ts到顶点s′,Te的路径p构成的集合.

具体的基于G′构建的CTG-tree索引的最短路径查询算法伪码如算法3所示.

算法3. 最短路径查询算法CTGQ(T,s,s′,I=[ts,ta]).

输入：基于G′构建的CTG-tree索引T，查询源点s，目的点s′，时间间隔I=[ts,ta]；

输出：s在时间间隔I内到达s′的最短时态路径距离.

① locates,Ts,s′,Te in T； /*Ts包含Vout(s)中大于或等于ts的最小时间值；Te包含Vin(s′)中小于或等于ta的最大时间值*/

② determines,Ts.leaf,s′,Te.leaf in T； /*s,Ts.leaf,s′,Te.leaf分别表示顶点s,Ts,s′,Te所属子图对应的叶子节点*/

③ if s,Ts.leaf(G′)=s′,Te.leaf(G′)=Gf/*s,Ts.leaf(G′),s′,Te.leaf(G′)分别表示顶点s,Ts,s′,Te所属叶子节点对应的子图*/

④ d

⑤ else if s,Ts.leaf(G′)=Gs,s′,Te.与s′,Te属于不同叶子节点对应的子图*/

⑥ dTs,uo)+d(uo,ui)+d(ui,s′,Te))；

⑦ end if

⑧ 输出d(s,Ts,s′,Te).

首先，算法在CTG-tree上查找s,Ts,s′,Te,将原始时态图上最短时态路径计算转化为压缩图上点s,Ts到点s′,Te的最短路径计算(行①).

接下来，确定顶点s,Ts,s′,Te所属子图对应的CTG-tree中的叶子节点s,Ts.leaf,s′,Te.leaf(行②).如果s,Ts,s′,Te同属一个子图Gf，则顶点s,Ts到s′,Te的最短路径有2种情况：

1) s,Ts到s′,Te的最短路径中的点均在子图Gf中，则在子图Gf中运用Dijkstra算法计算d(s,Ts,s′,Te)=Dijkstra(s,Ts,s′,Te,Gf)；

2) s,Ts到s′,Te的最短路径中的点部分属于其他子图Gx(≠Gf)，则最短路径必通过子图Gf的出边界点和入边界点，所以：

d(s,Ts,s′,Te)= d(bo,bi)+d(bi,s′,Te)；

其中，d(s,Ts,bo)，d(bo,bi)和d(bi,s′,Te可分别通过查找CTG-tree索引中子图Gf的游出距离矩阵Gi.Do，边界点距离矩阵Gi.Db和游入距离矩阵Gi.Di得到(行③～④).

如果s,Ts.leaf(G′)=Gs,s′,Te.leaf(G′)=即s,Ts,s′,Te隶属于不同叶子节点对应子图，则顶点s,Ts到s′,Te的最短路径：

d(s,Ts,s′,Te)= d(uo,ui)+d(ui,s′,Te));

令Ga是Gs对应叶子节点和对应叶子节点的最小公共祖先对应的子图，则Gl,Gr是Ga所在节点的孩子节点对应的子图，且s,Ts∈Gl,s′,Te∈Gr.上式中，d(uo,ui)可通过查找CTG-tree索引中图Ga的出边界点游入距离矩阵Ga.DBi得到；d(s,Ts,uo)根据下式计算：

其中，Gs-1对应节点是Gs对应节点的父节点，Gs-2对应节点是Gs-1对应节点的父节点，以此类推，Gl对应节点是G1对应节点的父节点.d(s,Ts,ux),d(ux-1,ux)，…，d(u1,uo)可分别通过Gs的游出距离矩阵Gs.Do，Gs-1的边界点游出距离矩阵Gs-1.DBo，…，Gl的边界点游出距离矩阵Gl.DBo得到.

d(ui,s′,Te)根据下式计算：

d(vx,s′,Te)))

，

其中，对应节点是Gr对应节点的孩子节点，对应节点是对应节点的孩子节点，以此类推，对应节点是对应节点的孩子节点.d(ui,v1),d(v1,v2)，…，d(vx-1,vx)，d(vx,s′,Te)可分别通过Gr的入边界点游入距离矩阵的入边界点游入距离矩阵的入边界点游

入距离矩阵和的游入距离矩阵得到.

以图2(a)所示时态图为例，查询顶点v5到v6在时间区间I=[1,10]内的最短时态路径.根据算法3，首先在G′中查找对应的点为v5，{8,9}和v6，10.而后在G′上计算v5，{8,9}到v6，10的最短路径.由于v5，{8,9}与v6，10隶属于同一叶子节点对应子图G5中，则计算Dijkstra(v5，{8,9},v6，10,G5)=1；min{d(v5，{8,9},v5，10)+d(v5，10,v3，7)+d(v3，7,v6，10),d(v5，{8,9},v5，10)+d(v5，10,v6，9)+d(v6，9,v6，10)}=∞;所以d(v5,v6,[1,10])=1.

若查询v1到v8在时间区间I=[1,15]内的最短时态路径,则转化为在G′上计算v1，1到v8，14的最短路径,由于v1，1∈G3，v8，14∈G6，v1，1与v8,14隶属于不同子图.则根据算法3有：

d(v1,1,v8,14)= d(uo,ui)+d(ui,v8,14))；

其中

∞;

所以最终，d(v1，1,v8，14)=d(v1，1,v1，2)+d(v1，2,v3，{5,6})+d(v3，{5,6},v3，7)+d(v3，7,v5，11)+d(v5，11,v8，14)=3.

算法3中，d(s,s′,I)的计算转化为压缩图上d(s,Ts,s′,Te)的计算，分为2种情况：1)当s,Ts,s′,Te同属一个子图时，时间复杂度为O(θ log θ);2)当s,Ts,s′,Te不属于同一子图时，需要迭代遍历s,Ts所在叶子节点对应子图Gs的游出距离矩阵，Gs对应节点的前驱节点相应子图Gs-1，Gs-2，…，Gl的边界点游出距离矩阵,Ga的出边界点游入距离矩阵，Gr的入边界点游入距离矩阵，Gr对应节点的后继节点相应子图的入边界点游入距离矩阵和s′,Te所在叶子节点对应子图的游入距离矩阵；所以时间复杂度为

|Gl.DBo|+|Gr.DIi|+|Gs.Do|+|Gs′.Di|).

5 实验分析

本节在真实的数据集上对所提出的CTGQ方法进行实验测试，并与2种流行方法1-pass[7]和TDFS进行对比，以验证CTGQ的效率.

5.1 实验设置

本文使用4个真实数据集进行实验测试，分别是GTFS数据集Transit(1)http://www.rtd-denver.com/services，以及SNAP公开的数据集Bitcoin(2)https://snap.stanford.edu/data/soc-sign-bitcoin-otc.html，Mathoverflow(3)https://snap.stanford.edu/data/sx-mathoverflow.html，Askubuntu(4)https://snap.stanford.edu/data/sx-askubuntu.html.Transit数据集记录了美国科罗拉多州丹佛县班车数据，包括班车号、班车出发时间、到达时间，停靠站点等信息.Bitcoin数据集是一个who-trust-whom网络，网络中的顶点表示在一个名为比特币OTC交易平台上使用比特币进行交易的用户；由于比特币用户是匿名的，为防止欺诈和风险用户交易，用户之间会进行声誉评分，因此网络中的边记录一个用户给另一个用户的声誉评分以及评分时间.Mathoverflow和Askubuntu数据集均为Stack Exchange下的互动时态网络，顶点表示用户，从用户u到用户v的边包含3种类型的互动关系:用户u在时间t回答了v的问题；用户u在时间t评论了v的问题；用户u在时间t评论了v的回答.表1给出了实验测试中用到数据集的统计信息.其中|VT|,|ET|,|T(GT)|分别表示时态图的顶点数、边数和时态区间数.对于每个数据集，随机选取500组查询，查询时间间隔默认为I=[0,+∞],报道每个算法的平均查询时间.

本文将CTGQ与1-pass[7]和TDFS进行对比.1-pass算法和和TDFS均无需构建索引，1-pass算法在转化图上运用Dijkstra算法计算最短时态路径；TDFS算法在原始时态图上进行深度优先遍历计算最短时态路径；实验测试过程中，为取得较好的索引性能和查询性能，4个数据集Transit，Bitcoin，Mathoverflow，Askubuntu默认参数l=16;θ分别设置为128，64，256，128.本文所有实验程序均使用C++语言编写，实验测试环境为一台配置为英特尔至强CPU处理器E5-2650 v4，128 GB内存，1 TB硬盘的服务器.

5.2 实验结果与分析

表2给出了原始数据集采用3.1节提出的规则进行转化和压缩后得到的转化图和压缩图的大小.与表1数据进行对比，可以看出转化图的顶点数是原始图顶点数的4～97倍，转化图的边数是原始图边数的2～4倍.相较于转化图，压缩图顶点数是转化图顶点的3～50倍，压缩图边数是转化图边数的2～3倍，说明了本文提出压缩规则的有效性.

表3给出了CTG-tree索引构建时间和空间代价.可以看出，Transit数据集上构建CTG-Tree索引需要时间不足1 s；Askubuntu数据集上构建CTG-tree索引需要时间接近8 min.在4个真实数据集上，CTG-tree索引大小在20 MB到8.2 GB之间.

表4给出了CTGQ,1-pass和TDFS算法在4个数据集上的平均查询时间.由表4可以观察出，CTGQ查询时间比1-pass平均快1个数量级，比TDFS平均快2个数量级.这是因为1-pass算法与TDFS算法均需要在线遍历搜索，1-pass算法需要在转化图上运用Dijkstra算法计算2点之间的最短时态路径;TDFS算法在计算最短时态路径时，由于最短时态路径的子路径不满足最优子结构性质，所以TDFS需要遍历的时态路径是指数级的，耗时更长；而CTGQ利用了CTG-tree索引进行查询，查询过程中无需再遍历压缩图，只需要根据CTG-tree索引矩阵即可得到结果，因此效率更高.

本文实验验证了4个不同的时间间隔Ii(1≤i≤4)对最短时态路径查询时间的影响.I1是数据集的最大时间间隔，Ii+1(1≤i≤3)是将Ii划分为2个相等子区间后的第一个子区间.图5给出了CTGQ,1-pass和TDFS算法在Transit，Bitcoin，Mathoverflow，Askubuntu数据集上的实验结果.

从图5可以看到，CTGQ，1-pass和TDFS的查询时间随着时态区间的缩减而降低，TDFS下降趋势最为显著.这是因为时态区间缩减时，TDFS所需遍历的时态路径数目大幅度减少；而1-pass和CTGQ算法在压缩图上计算，时态区间减小时，1-pass算法遍历的路径长度减小，CTGQ算法遍历的CTG-tree矩阵索引计算量减少.

另外，从图5还可以观察到不同查询时态区间下，CTGQ算法的性能始终远远优于1-pass和TDFS算法的性能，这与前述实验分析结论一致.

本文考察了叶子子图顶点数目阈值θ、迭代划分子图数目l对CTG-tree构建和CTGQ算法运行性能的影响.表5给出了4个数据集Transit，Bitcoin，Mathoverflow，Askubuntu在θ值分别设置为2，4，8，16，l值分别设置为32，64，128，256，512情况下的CTG-tree索引构建时间和CTGQ算法运行时间结果.

首先由表5可以看到，当l取固定值时，CTG-tree索引构建时间随着θ值增加呈减少趋势.这是因为θ值增加，CTG-tree叶子节点对应子图的顶点数目增多，迭代划分产生的总子图数目减少，相应的入边界点、出边界点总数减少，索引矩阵计算量减少，因此CTG-tree索引构建时间降低.

其次，由表5可以看出，当θ取固定值时，CTG-tree索引构建时间随着l值增大基本呈先降低再升高的趋势.这是因为随着l值的增大，CTG-tree每层节点数目增多，入边界点、出边界点总数先减少再增多，导致索引矩阵计算量先减小后增加.

此外，当θ取固定值时，CTGQ算法运行时间随着l值增大基本呈降低趋势.这是因为，l值增大，CTG-tree高度降低，CTGQ算法自底向上，自顶向下遍历层数减少.

鉴于上述观察，为取得较好的索引性能和查询性能，4个数据集默认参数l=16;θ在数据集Transit，Bitcoin，Mathoverflow，Askubuntu上的值分别设置为128，64，256，128.

6 总 结

本文研究了时态图最短路径问题并提出了基于CTG-tree索引的计算方法，其主要包含预处理阶段和在线查询阶段.在预处理阶段，本文提出了一种无损压缩方法和层次索引CTG-tree.其首先将时态图转化为普通图，对普通图进行无损压缩以减小图处理规模，将时态图上最短路径计算转化为在压缩图上执行；而后对压缩图采用Metis划分将压缩图层次划分为若干个子图，得到每个子图的入边界点与出边界点集合，并基于此构建CTG-tree.CTG-tree为每个叶子节点对应子图计算游入距离矩阵、游出距离矩阵和边界点距离矩阵；为每个非叶节点对应子图计算出边界点游入距离矩阵，入边界点游入距离矩阵和边界点游出距离矩阵.查询阶段本文基于CTG-tree索引设计了高效的最短路径查询算法.最后，在真实的时态图数据集上进行了全面的实验，实验结果验证了本文所提出的基于CTG-tree索引的算法的效率.此外，设计高效的分布式时态图最短路径方法与增量计算算法也是一个重要且值得研究的问题，后续工作计划对其进行深入地探索.

作者贡献声明：张天明负责问题定义、方法设计、数据分析与论文撰写修改工作；徐一恒负责数据收集与整理、实验结果可视化工作；蔡鑫伟负责部分实验测试和整理工作；范菁负责指导论文写作并提出修改建议.

参考文献

[1]Bast H, Delling D, Goldberg A, et al. Route planning in transportation networks[M] //Algorithm Engineering. Berlin: Springer, 2016: 19-80

[2]Wang Yong, Li Guoliang, Tang Ning. Querying shortest paths on time dependent road networks[J]. Proceedings of the VLDB Endowment, 2019, 12(11): 1249-1261

[3]Huo Wenyu, Tsotras V J. Efficient temporal shortest path queries on evolving social graphs[C] //Proc of the Int Conf on Scientific and Statistical Database Management. Berlin: Springer, 2014: 38:1-38:4

[4]Ding Bolin, Yu J X, Qin Lu. Finding time-dependent shortest paths over large graphs[C] //Proc of the Int Conf on Extending Database Technology: Advances in Database Technology. New York: ACM, 2008: 205-216

[5]Yuan Ye, Lian Xiang, Wang Guoren, et al. Constrained shortest path query in a large time-dependent graph[J]. Proceedings of the VLDB Endowment, 2019, 12(10): 1058-1070

[6]Wu Huanhuan, Cheng J, Huang Silu, et al. Path problems in temporal graphs[J]. Proceedings of the VLDB Endowment, 2014, 7(9): 721-732

[7]Wu Huanhuan, Cheng J, Ke Yiping, et al. Efficient algorithms for temporal path computation[J]. IEEE Transactions on Knowledge & Data Engineering, 2016, 28(11): 2927-2942

[8]Zhong Ruicheng, Li Guoliang, Tan K L, et al. G-tree: An efficient and scalable index for spatial search on road networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(8): 2175-2189

[9]Panda M, Mishra A. Asurvey of shortest-path algorithms[J]. International Journal of Applied Engineering Research, 2018, 13(9): 6817-6820

[10]Zwick U. Exact and approximate distances in graphs—A survey[C] //Proc of European Symp on Algorithms. Berlin: Springer, 2001: 33-48

[11]Hansen P. Bicriterion path problems[M] //Multiple criteria decision making theory and application. Berlin: Springer, 1980: 109-127

[12]Dantzig G B, Thapa M N. Linear programming 2: Theory and extensions[M]. Berlin: Springer, 2006

[13]Batz G V, Geisberger R, Neubauer S, et al. Time-dependent contraction hierarchies and approximation[C] //Proc of the Int Symp on Experimental Algorithms. Berlin: Springer, 2010: 166-177

[14]Potamias M, Bonchi F, Castillo C, et al. Fast shortest path distance estimation in large networks[C] //Proc of the 18th ACM Int Conf on Information and Knowledge Management. New York: ACM, 2009: 867-876

[15]Akiba T, Iwata Y, Yoshida Y. Fast exact shortest-path distance queries on large networks by pruned landmark labeling[C] //Proc of the ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2013: 349-360

[16]Geisberger R, Sanders P, Schultes D, et al. Contraction hierarchies: Faster and simpler hierarchical routing in road networks[C] //Proc of the Int Workshop on Experimental and Efficient Algorithms. Berlin: Springer, 2008: 319-333

[17]Botea A. Ultra-fast optimal pathfinding without runtime search[C] //Proc of the Conf on Artificial Intelligence and Interactive Digital Entertainment. Palo Alto, CA: AAAI, 2011: 122-127

[18]Botea A, Harabor D. Path planning with compressed all-pairs shortest paths data[C] //Proc of the Int Conf on Automated Planning and Scheduling. Palo Alto, CA: AAAI, 2013: 293-297

[19]Geisberger R, Sanders P, Schultes D, et al. Exact routing in large road networks using contraction hierarchies[J]. Transportation Science, 2012, 46(3): 388-404

[20]Ouyang Dian, Yuan Long, Qin Lu, et al. Efficient shortest path index maintenance on dynamic road networks with theoretical guarantees[J]. Proceedings of the VLDB Endowment, 2020, 13(5): 602-615

[21]Delling D, Goldberg A V, Pajor T, et al. Customizable route planning in road networks[J]. Transportation Science, 2017, 51(2): 566-591

[22]Zhang Dongxiang, Yang Dingyu, Wang Yuan, et al. Distributed shortest path query processing on dynamic road networks[J]. The VLDB Journal, 2017, 26(3): 399-419

[23]Hassan M S, Aref W G, Aly A M. Graph indexing for shortest-path finding over dynamic sub-graphs[C] //Proc of the 2016 Int Conf on Management of Data. New York: ACM, 2016: 1183-1197

[24]Thorup M, Zwick U. Approximate distance oracles[J]. Journal of the ACM, 2005, 52(1): 1-24

[25]Elkin M, Peleg D. (1+ε,β)-spanner constructions for general graphs[J]. SIAM Journal on Computing, 2004, 33(3): 608-631

[26]Wang Sibo, Lin Wenqing, Yang Yi, et al. Efficient route planning on public transportation networks: A labelling approach[C] //Proc of the ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2015: 967-982

[27]Wu Huanhuan, Huang Yuzhen, Cheng J, et al. Reachability and time-based path queries in temporal graphs[C] //Proc of the Int Conf on Data Engineering (ICDE). Piscataway, NJ: IEEE, 2016: 145-156

A Shortest Path Query Method over Temporal Graphs

Zhang Tianming1, Xu Yiheng1, Cai Xinwei2, and Fan Jing1

1(College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023) 2(College of Computer Science and Technology, Zhejiang University, Hangzhou 310013)

Abstract Shortest path query has been extensively studied for decades of years. However, most of existing works focus on shortest path query over general graphs, a paucity of studies aim at temporal graphs, where there are multi-edges between two nodes and each edge is associated with a temporal interval, recording the start time and the end time of an event. Shortest path query over temporal graphs has a plethora of applications in urban traffic route planning, social network analysis, and communication network mining, to name but a few. Traditional shortest path algorithms on general graphs are not suitable for temporal graphs because subpaths of a shortest temporal path are not guaranteed to be the optimal substructures. Hence, in this paper, we propose a Compressed Transformed Graph tree (CTG-tree) based query method, which consists of a preprocessing stage and an online query stage. In the preprocessing stage, we transform the temporal graph into a general graph, propose a lossless compression method to reduce the scale of the transformed graph, use hierarchical partitioning technique to divide the compressed directed graph into subgraphs, and then build a CTG-tree index based on the partitioned subgraphs. The nodes of CTG-tree maintain shortest paths between some vertices in the corresponding subgraphs，save shortest paths between boundaries in the subgraphs of children nodes, and record shortest paths between boundaries of the subgraphs corresponding to the children nodes and those corresponding to the current node. In the online query stage, based on the constructed CTG-tree index, we develop an efficient shortest temporal path query method. Using four real-life temporal graphs, we experimentally demonstrate that our proposed method has the best query performance compared with the state-of-the-art methods.

Key words shortest path; temporal graph; compressed directed graph; tree index; query method

Zhang Tianming, born in 1988. PhD, lecturer. Member of CCF. Her main research interests include graph data management and deep learning.

Xu Yiheng, born in 2000. Bachelor candidate. His main research interests include graph querying and processing.

Cai Xinwei, born in 1998. Master candidate. His main research interests include graph analysis and mining.

Fan Jing, born in 1969. PhD, professor, PhD supervisor. Distinguished member of CCF. Her main research interests include middleware, virtual reality and visualization.

(tmzhang@zjut.edu.cn)

收稿日期：2021-08-31；修回日期：2021-11-05

基金项目：国家重点研发计划项目(2018YFB1402802)

This work was supported by the National Key Research and Development Program of China (2018YFB1402802).

通信作者：范菁(fanjing@zjut.edu.cn)

中图法分类号 TP311.131

张天明，1988年生.博士，讲师，CCF会员.主要研究方向为图数据管理和深度学习.

徐一恒，2000年生.本科生.主要研究方向为图查询处理.

蔡鑫伟，1998年生.硕士研究生.主要研究方向为图分析与挖掘.

范 菁，1969年生.博士，教授，博士生导师，CCF杰出会员.主要研究方向为中间件、虚拟现实和可视化.