时态图最短路径算法

原论文：Spatio-temporal Network Databases and Routing Algorithms: A Summary of Results

时态图发展需要解决的问题：

1、所消耗的存储空间将增大，需要消除冗余，增加存储效率。

2、旧的数据模型在时态图上可能会有新的解释。如寻找两点之间最短的路径可能有两种解释：（1）给定起始节点与起始时间寻找最短路径。（2）寻找两个点间消耗最短的路径，起始时间随意。

3、设计高效正确的查询处理策略，因为一些常用的图策略可能不适用于时态图。如最优子图结构可能在时态图不适用。

时态图寻找最短路径的挑战：

网络可能在对图进行遍历的时候进行更改。边的属性会变，边是否存在也会变。如在t=1的时刻，从a到b的旅行时长可能为2，但是在t=2的时刻旅行时长就变为了1，在t=3的时刻改边就不存在了。

一个时态图的表示方式：

如上所示，N表示节点集合，E表示边集合，TF表示整个时间间隔，fi表示时间序列与节点的匹配（个人理解应该是在i时刻节点是否存在❓），gi对应边与时间序列的匹配，wi表示不同时间边的权重。

（个人理解可能有误，以上面原文为准）

两种时态图的图形表示方式：

【1】

上图(d)表示了time aggregated graph，他是将图（a），（b），（c）合并起来的图，每个边有两个属性，如边N1，N2第一个属性（1，2）表示边存在的时间，第二个[1,1,-]表示边在对应时间的权重。

【2】

上图（b）表示了一个时间序列的图的节点之间的时态情况，如N1,N2，在t=1的时候权中为1，所以（b）中N1在t=1的时刻指向t=2时刻的N2，但是这存在一个问题就是t越大，则计算所消耗的时间将会越长。

时态图寻找最短路径的两种算法：

【1】SP-TAG

简单翻译一下：

输入：G(N, E)，N为节点集，E为边集。

       其中，节点n有属性：“存在时间序列”

              边有属性：“存在时间序列”，“旅行时长序列”

σu,vt表示边（u，v）在t时刻的旅行时长。

输出：在tstart时刻出发，从s到d的最短路径.

       初始：c[s]= tstart，对于任意不为s的节点v，c[v]=∞（c[u]表示在节点u处的时间点）

       将s插入队列 Q,

       当Q不为空时：

              取出队列Q中最小的节点u，

              对于每一个u的相邻节点v：

                     t为（u，v）和c[u]中较小的值

                     如果t+t<c[v]

                            则将c[v]的值修改为t+，并将v的父节点设为u，将v插入  Q   

（上面的min_t((u，v), c[u]）我没太清楚想表达什么意思，但算法的意思大致是如果t=3时刻到了节点N4（如下图），但是在此时边（N4,N5）之间是不能通行的，因此需要等候到t=5）

此算法适用于节点在不同的是时间点的存在情况不同，如下图所示：

该图的解答过程如下所示：

在t=1的时刻开始从N1出发更新后继节点。

此算法时间复杂度为：O(m(logT+logn))，T为时间戳个数，n是节点个数，m是边的个数。

【2】Best算法：

给定起始节点，选择一个最合适的开始时间，使得花费的时间最少，每条边在不同时间所消耗的时长是变化的。

算法如图所示：

对于下面这样一个图，从终点向前更新，节点的第一排数字表示总花费的时长，第二排数字表示下一跳节点。

具体的更新过程如下所示：

该算法时间复杂度为O(n2mT)，n为节点数，m为边的数目，t为时间戳数目。