论文名称：Path Problems in Temporal Graphs

论文研究背景

        现有的路径问题基本都是在静态图上来进行研究的，然而经典最短路径的概念在时间图中是不充分的，甚至是有缺陷的，因为时间信息决定了沿着任何路径的活动的顺序。那么能否提出有效的算法来计算时序图上的最短路径问题了，本文就主要给出了两种方法，并对其进行实验验证。

论文内容

        在本文中在时间图中定义了四种类型的路径，统称为最小时间路径，因为它们给出了不同度量的最小值：(1)最早到达路径(即从源x到目标y给出最早到达时间的路径);(2)最晚出发路径(即从x出发的最晚出发时间，以便在给定时间到达y的路径);(3)最快路径(即从x到y所用时间最短的路径);和(4)最短路径(即从x到y的最短路径，从边的总遍历时间来看)。

        然后使用了两种方法来求时序图的最小时间路径：单遍历算法和图转换方法，这也是本篇论文的核心。

 ONE-PASS ALGORITHMS ：

       在介绍单遍算法之前，必须要对它进行边流表示， 就是时序图G中所有边的序列的集合，按照开始时间的顺序进行排列。例如，{(v3, v2, 1,1)， (v1, v2, 2,5)， (v2, v4, 4,1)}就是边流表示，是严格按照时间升序的。

1.Earliest-Arrival Paths

它就是使用一个数组t[v]来保持从x到流中已经看到的每个顶点v∈V的当前最早到达时间，然后对G进行线性扫描，对于流中的每一条传入边e = (u, v, t, λ)，我们检查e是否满足[tα， tω]内时间路径的时间约束，如果是，我们通过边e扩展到v来增长时间路径。在此过程中，如前所述，我们在必要时更新t[v]。当我们遇到流中起始时间大于或等于tω的第一个边时，流程终止。使用O(n+M)时间和O(n)空间。

2.Latest-Departure Paths

 与算法1类似，不过是计算其余点到x的最晚出发时间

3.Fastest Paths

        在边流表示中给出了两种方法，第一种是用一个集合S来记录起始点的所有出发时间，用f[v]来记录最快路径，然后对于每个起始时间都调用算法1，来更新f[v]。这种方法多次调用算法1，可能会有很多潜在的冗余处理，需要O(|S|(n + M))时间和O(n)空间。

       第二种方法只会扫描一次图， 为v创建一个排序列表 Lv，其中Lv的一个元素是一对(s[v]， a[v])，其中s[v]是路径P从x到v的起始时间，a[v]是路径P到达v的时间，用作Lv排序的键。

 根据这条引理，我们可以修建被占优元素，从而不影响最快路径

          我们扫描一次输入图的边流。对于每个传入边e = (u, v, t， λ)，我们检查从x到u的最早到达路径是否可以在[tα， tω](第5行)内通过e扩展到v。如果是，我们选择从x到u的路径，其到达时间在t时或之前(第9行)最大。然后 根据上面引理不断修剪Lv中的被占优元素，如果最小持续时间f[v]发生变化，就更新f[v]的值。O(n + M log c)时间和O(min{n|S|， n + M})空间。

4.Shortest Paths

和最快路径算法相似，只不过Lv中的元素为(d[v]， a[v])，其中d[v]为路径P从x到v的距离，用作在Lv排序的键，a[v]为路径P到达v的时间，d[v]和a[v]越小就越占优，然后进行修剪

 A GRAPH TRANSFORMATION APPROACH

        将时序图转换为静态图，转换之后，顶点还要记录到达时间，到自身的边权值记为0。发出边的点记为Vout(v)，到达边的顶点记为Vin(v)

 对于Earliest-Arrival Paths，创建了一个顶点x0在˜G（转换之后的静态图）中，和一个从x0到每个顶点(x, t)∈G中的Vout(x)的有向边，其权重为0，简单地从源顶点x0运行广度优先搜索(BFS)算法

而Latest-Departure Paths进行反向BFS遍历就可求出

对于Fastest Paths，创建了一个顶点x0在˜G中，和一个从x0到每个顶点(x, t)∈G中的Vout(x)的有向边，其权重为0设S = {(x, t): (x, t)∈Vout(x)， tα≤t≤tω}，其中S中的元素按时间降序排序。从x0开始，我们首先访问S中时间最长的顶点，即(x, t1);然后从(x, t1)开始进行BFS，计算从x到每v的最早到达时间t[v]，得到这条最早到达路径的持续时间为(t[v]−t1)。然后，我们用第二大时间访问S中的顶点(x, t2)我们从(x, t2)开始进行BFS，但我们不会从之前访问过的任何顶点继续BFS。我们重复这个过程，直到处理S中的所有顶点。G中从x到每v的最快路径的持续时间是所有从x到v的最早到达路径的最短持续时间。

Shortest Paths，转换之后最短路径和静态图定义相同，直接使用Dijkstra算法

总结

        本文就主要讲了这两种方法来研究时序图中的路径问题，当然还提到一些应用和实验结果，由于对照的实验是一篇04年的文章，它使用贪婪策略和枚举的方法，比本文的算法效率要慢得多，这里就不详细说明了，主要还是明白算法的思想。

        看完这篇文章，收获还是很多的，边流表示只需要一次扫描就能解决路径问题，而图转换可以直接使用静态图的路径研究方法，大大降低了问题的复杂度，但是牺牲了大量的空间。对于时态图，消耗时间和空间都是要注意的地方。