时变网络中最短路径的故障修复问题

Fault Repair of the Shortest Path in the Time-Varying Networks

摘要: 在交通和通信网络中，最短路径及其相关优化问题具有广阔的应用前景。而基于大规模网络的时变特性，时变最短路问题被逐渐关注并且进行了广泛研究。另外，为保证传输性能，当最短路径中存在链路或节点故障时，就需要对该路径进行快速恢复和重建，即需要根据故障影响范围制定切实可行的恢复机制使网络正常运行。进一步，为了提高网络服务质量，需要尽量降低路径恢复成本。因此，本文对时变网络中含有一条故障边的最短路径快速修复问题进行了研究，并提出了有效算法。该算法不仅保证了时变网络中沿路径经过时边赋权函数的时间连续性，而且充分利用了时变最短路子图，在保证传输连续性的基础上减少计算复杂度。最后得出，对于具有n个顶点和m条边的时变网络，算法的时间复杂度为，其中表示路径所有出发时间区间内受影响区间点数目的最大值，表示所有出发时间区间内受影响区间点和受影响区间边总数的最大值。

Abstract: In transportation and communication networks, the shortest path and its related optimization problems have broad application prospects. Based on the time-varying feature of large-scale networks, the time-varying shortest path problem has been gradually concerned and widely studied. In addition, in order to ensure the transmission performance, when there is a link or node failure in the shortest path, it is necessary to quickly recover and reconstruct the path, that is, it is necessary to formulate a feasible recovery mechanism according to the occurrence of failure to make the network operate normally. Further, in order to improve the quality of network service, it is necessary to minimize the cost of path recovery. Therefore, this paper studies the shortest path fast repair problem with a fault edge in time-varying networks, and proposes an effective algorithm. The algorithm not only ensures the time continuity between edges along the path in the time-varying network, but also makes full use of the time-varying shortest path subgraph to reduce the computational complexity. Finally, for the time-varying network with n vertices and m edges, the time complexity of the algorithm is , in which represents the maximum number of affected interval nodes in all departure time intervals of the path, and represents the maximum number of affected interval nodes and affected interval edges in all departure time intervals.

1. 引言

图论是建立网络拓扑模型的基本数学工具，在加权图中寻找最短路径是图论中最基本的问题之一，该问题在通信网络、工厂设施布局以及超大规模集成电路设计中得到了广泛的应用 [1] [2] [3] [4]。该问题一般用来求解两顶点之间或从单一源点到其他所有点的最短路径。根据边权值是否为负，可以通过Dijkstra算法或Bellman-Ford算法求解 [5]。

然而当故障发生时，如何提高网络生存性并保持服务连续性是网络界面临的一个重大挑战。通常情况下，为了降低路径恢复成本(时间或能耗)，设计路径恢复方案成为亟待解决的问题。如果在两个指定节点之间存在多条路径，则可将其中一条路径视为主动路径，而另外的一条路径可当作备份路径。然而额外构造起点到终点之间的备份路径通常会产生较高的时间复杂度。因此，局部修复的重要性尤为突出。即如果在某个时间点或者某段时间内最短路径上的一个或者多个链路发生故障时，那么从链路故障处开始寻找局部备份路径可以有效降低路径恢复时间。

事实上，当故障发生时可视为将故障边的权值调整为无穷大，此过程通常被称为图更改，而该类问题的更一般化版本包含权值增加、权值减少、边插入和边删除。后两种变化在概念上可以考虑为权值变化的特殊情况。因此，如果变化过程只包含权值的增加和边的删除，被称为增量问题；如果它只包含权值减小和边插入，被称为递减问题，这两类问题都属于半动态问题。当变化过程同时包含权值增加和权值减小，则被称为完全动态问题。如果每次只有一条边发生改变，称为单边问题，而如果多条边同时改变，则称为批处理问题。关于图中的这种动态最短路径问题已有大量的研究 [6] - [13]。 [1] [8] [12] [14] 提出了几种算法来解决单变问题。在 [1] [11] [15] 中考虑了批处理问题。其中，文献 [12] 中，Ramalingam和Reps根据自适应参数 $\Vert \delta \Vert$ 来分析增量算法，该值可以衡量图改变规模的大小，并提出运行时间为 $O\left(\Vert \delta \Vert +\left|\delta \right|\log \left|\delta \right|\right)$ 的有效算法。同样，文献 [14] 给出了复杂性为 $O\left(\sqrt{m}\log n\right)$ 的有效算法，其中n为顶点数，m为边数。

在时变网络中，静态网络的最短路算法和路径恢复方案均不再适用，因此在时变网络中的路径优化和恢复有很重要的研究意义。Li等人 [16] 在2019年提出了一种在线近似技术AT-Dijkstra和自下而上压缩方法，将跳标记方法(hop-labeling)扩展到时变环境中，并给出了相应的查询算法。Wang等人 [17] 设计了一个颇为有效的时变最短路径查询算法(TDSP)，用于查找任意出发时刻的最优路径，该算法的时间复杂度是 $O\left({\log }^2{k}_f\cdot \left|V\right|\cdot {\log }^2\alpha \left(T\right)\right)$，其中 $\alpha \left(T\right)$ 表示总时间范围 $\left[0,T\right]$ 被分为的子时间段个数。之后，基于TDSP查询算法，他们给出了一个时间间隔最短路径查询(TIP)算法，用于查找出发时间在一个固定时间段内的最优路径并输出最优出发时刻，该算法的时间复杂度是 $O\left({\log }^2{k}_f\cdot \left|V\right|\cdot \alpha {\left(I\right)}^2\right)$。基于此，本文将进一步研究时变最短路径的快速恢复方案并给出算法框架，该算法时间复杂度为 $O\left(\alpha \left(T\right)\cdot \left[{\Vert \delta \Vert }_t+{\left|\delta \right|}_t\cdot \log {\left|\delta \right|}_t\right]\right)$。

本文主要使用了时变自适应参数 ${\Vert \delta \Vert }_t$ 度量在t时刻出发时网络规模的变化量并在局部范围内对时变路径进行修复，提出了在时变网络中修复最短路径的有效方法，通过选择受影响区间点和受影响区间边减少了计算复杂度，进一步寻找到故障修复后的时变最短路。

在给出主要算法的过程中，重点研究了时变赋权函数的应用，路径修复的时间连续性以及有效的时间段划分，同时充分利用了自适应参数降低算法复杂度，并进一步说明了局部修复算法的有效性和应用价值。

2. 模型概述

一个时变的网络通常都被模型化为一个时变的有向图 $G\left(V,E,W,T\right)$。

· V是G的顶点集， $\left|V\right|=n$；

· E是边集， $\left|E\right|=m$；

· $W=\left\{w_e\left(t\right):e\in E\right\}$，其中 $w_e\left(t\right):\left[0,T\right]\to R^{+}$ 表示边e关于出发时间t的时变旅行函数；

· T是给定的出发时间上界。

本文考虑的时变是边权值随时间连续变化的情况，且边的权值表示边的经过时间。因此，在本文中，边权函数被假定为是一个非负的连续线性分段函数。

在该时变网络中， $v_1{v}_n$ -路径被表示为 $P_{v_1{v}_n}\left(t\right)=\langle v_1,v_2,\cdots ,v_n\rangle$，表示在t时刻出发时从 $v_1$ 到 $v_n$ 的一条路径。其中 $v_1$ 是路 $P_{v_1{v}_n}\left(t\right)$ 的源点， $v_n$ 是路 $P_{v_1{v}_n}\left(t\right)$ 的汇点。

$P_{v_1{v}_{n-1}}\left(t\right)$ 表示从 $v_1{v}_n$ -路 $P_{v_1{v}_n}\left(t\right)$ 中删除点 $v_n$ 时形成的一条 $v_1{v}_{n-1}$ 子路径。

现在我们定义路的旅行时间函数和到达时间函数。给定路 $P_{v_1{v}_{n-1}}\left(t\right)$，该路的旅行时间函数和到达时间函数分别表示为 $w_{P_{v_1{v}_n}}\left(t\right)$ 和 $l_{P_{v_1{v}_n}}\left(t\right)$。

· $w_{P_{v_1{v}_n}}\left(t\right)$ 被递归地定义为：

$w_{P_{v_1{v}_n}}\left(t\right)=w_{P_{v_1{v}_{n-1}}}\left(t\right)+w_{\left(v_{n-1},v_n\right)}\left(l_{P_{v_1{v}_{n-1}}}\left(t\right)\right)$,

其中 $w_{P_{v_1{v}_n}}\left(t\right)$ 表示在t时刻出发时沿路径 $P_{v_1{v}_{n-1}}\left(t\right)$ 的旅行时间加上边 $\left(v_{n-1},v_n\right)$ 的旅行时间。

· $l_{P_{v_1{v}_n}}\left(t\right)$ 被递归地定义为：

$l_{P_{v_1{v}_n}}\left(t\right)=l_{P_{v_1{v}_{n-1}}}\left(t\right)+w_{\left(v_{n-1},v_n\right)}\left(l_{P_{v_1{v}_{n-1}}}\left(t\right)\right)$,

其中 $l_{P_{v_1{v}_n}}\left(t\right)$ 表示在t时刻出发时沿路径 $P_{v_1{v}_{n-1}}\left(t\right)$ 到达 $v_{n-1}$ 的到达时间加上边 $\left(v_{n-1},v_n\right)$ 的旅行时间。同时，点 $v_n$ 沿路径 $P_{v_1{v}_n}\left(t\right)$ 的到达时间函数被表示为： $l_{P_{v_1{v}_n}}\left(t\right)=t+w_{P_{v_1{v}_n}}\left(t\right)$。特别地， $l_{P_{v_1{v}_1}}\left(t\right)=t$。

本文中，令 ${\mathcal{P}}_{v_1{v}_n}\left(t\right)$ 表示当出发时间为t时从 $v_1$ 到 $v_n$ 的所有路径集合。 $w_{v_1{v}_n}^{*}\left(t\right)$ 表示当出发时间为t时从 $v_1$ 到 $v_n$ 的最短旅行时间函数， $l_{v_n}^{*}\left(t\right)$ 表示当出发时间为t时 $v_n$ 的最早到达时间函数。则

$w_{v_1{v}_n}^{*}\left(t\right)=\min \left\{w_P\left(t\right)|P\left(t\right)\in {\mathcal{P}}_{v_1{v}_n}\left(t\right)\right\}$

$l_{v_n}^{*}\left(t\right)=\min \left\{l_P\left(t\right)|P\left(t\right)\in {\mathcal{P}}_{v_1{v}_n}\left(t\right)\right\}$

假设 $P_{v_1{v}_n}^{*}\left(t\right)=\arg \min \left\{w_P\left(t\right)|P\left(t\right)\in {\mathcal{P}}_{v_1{v}_n}\left(t\right)\right\}$。显然， $l_{v_n}^{*}\left(t\right)=w_{P_{v_1{v}_n}^{*}}\left(t\right)+t=w_{v_1{v}_n}^{*}\left(t\right)+t$。因此 $P_{v_1{v}_n}^{*}\left(t\right)$ 称为对应于 $w_{v_1{v}_n}^{*}\left(t\right)$ 和 $l_{v_n}^{*}\left(t\right)$ 的路径。

本文考虑的图均为无重边且无负环的简单有向图，且本文只考虑满足先进先出(FIFO)性质的网络，即对于任意出发时刻 $t,t^{\prime }$，如果 $t<t^{\prime }$，则 $t+w_{v_1{v}_n}^{*}\left(t\right)<t^{\prime }+w_{v_1{v}_n}^{*}\left(t^{\prime }\right)$。

接下来，我们先给出时变网络中求单条最短路的两个问题定义。

定义2.1 (时变最短路径查询(TDSP) [17] )。给定一个时变网络图 $G\left(V,E,W,T\right)$，源点为 $v_s$，汇点为 $v_d$，t为出发时刻。TDSP查询就是找出发时间t对应的最短旅行时间函数 $w_{v_s{v}_d}^{*}\left(t\right)$ 和相应的最短路径 $P_{v_s{v}_d}^{*}\left(t\right)$。

定义2.2 (时间间隔最短路径查询(TIP) [17] )。给定一个时变网络图 $G\left(V,E,W,T\right)$，源点为 $v_s$，汇点为 $v_d$， $I=\left[t,t^{\prime }\right]$ 为出发时间区间。TIP查询就是找区间I内的最优出发时间 $t^{*}$，最短旅行时间函数 $w_{v_s{v}_d}^{*}\left(t^{*}\right)$ 和对应的最短路径 $P_{v_s{v}_d}^{*}\left(t^{*}\right)$。

由于本文要解决的是时变单故障边最短路径修复问题，设故障为边 $\left(v_x,v_y\right)$ 在时间段L内发生故障，则将该故障表示为 $\mathcal{F}=\left[\left(v_x,v_y\right),L\right]$。下面将给出本文要解决的问题定义。

定义2.3 (时变单故障边最短路径修复问题)。给定一个时变网络图 $G\left(V,E,W,T\right)$，源点为 $v_s$，汇点为 $v_d$，设故障 $\mathcal{F}=\left[\left(v_x,v_y\right),L\right]$，则时变单故障边最短路径修复问题是在给定任意 $\mathcal{F}$ 后找出从 $v_s$ 到 $v_d$ 的最短修复路径。

3. 算法方案：单链路故障情形下找时变的故障修复最短路径

3.1. 算法引入

网络图 $G\left(V,E,W,T\right)$ 中一般包含四种类型的图更改：权重增加、权重减少、边插入和边删除。本文主要针对删边这种边的变化情况给出时变情形下的修复算法。主要符号及说明见表1。

Table 1. Main symbol and description

表1. 主要符号及说明

在本文中，对于任意点 $v_i\in V\left(G\right)$，当出发时刻 $t\in I$ 时，将 $v_i\left(t:I\right)$ 称为区间点，表示当出发时刻 $t\in I$ 时考虑点 $v_i$。而对于任意边 $\left(v_i,v_j\right)\in E\left(G\right)$，当出发时刻 $t\in I$ 时，将 $\left(v_i,v_j\right)\left(t:I\right)$ 称为区间边，表示当出发时刻 $t\in I$ 时考虑边 $\left(v_i,v_j\right)$。 $SP\left(t:I\right)$ 表示当出发时刻 $t\in I$ 时从节点 $v_s$ 到其它所有点的最短路构成的图G的子图，称为当 $t\in I$ 时的最短路子图。由于本文的算法主要是对故障进行路径修复，因此，当某条边发生故障时，不可避免地会有一些边或点受到影响。这就说明故障的发生会导致 $SP\left(t:I\right)$ 子图产生相应的改变，比如删除某些受到影响的区间边或更新某些区间点的最早到达时间函数。进一步地，在本文中，对任意点 $v_j\in V\left(G\right)$， $l_{v_j}^{*}\left(t:I\right)$ 表示为当出发时间 $t\in I$ 时从 $v_s$ 到 $v_j$ 的更新前的最早到达时间， $l_{v_j}\left(t:I\right)$ 表示为当出发时间 $t\in I$ 时从 $v_s$ 到 $v_j$ 的更新过程中的最早到达时间， ${l^{\prime }}_{v_j}\left(t:I\right)$ 表示为当出发时间 $t\in I$ 时从 $v_s$ 到 $v_j$ 的更新后的最早到达时间。据此，我们给出本文中受影响区间点集和受影响区间边集的定义。

定义2.1 (受影响区间边集 $E_{\delta }\left(t:I\right)$ )。在 $SP\left(t:I\right)$ 中，如果在时间段L内删除故障边 $\left(v_x,v_y\right)\left(t:I\right)$ 之后，新的最短路子图中不存在经过 $\left(v_i,v_j\right)\left(t:I\right)$ 的时变 $v_s{v}_j$ -路或经过边 $\left(v_i,v_j\right)\left(t:I\right)$ 但 ${l^{\prime }}_{v_j}\left(t:I\right)\ne l_{v_j}^{*}\left(t:I\right)$，则称边 $\left(v_i,v_j\right)\left(t:I\right)$ 为受影响区间边， $E_{\delta }\left(t:I\right)$ 为当出发时间 $t\in I$ 时所有受影响区间边的集合。

定义2.2 (受影响区间点集 $V_{\delta }\left(t:I\right)$ )。在 $SP\left(t:I\right)$ 中，如果在时间段L内删除故障边 $\left(v_x,v_y\right)\left(t:I\right)$ 之后，以点 $v_j$ 为头节点的边是受影响区间边，则称点 $v_j$ 为受影响区间点， $V_{\delta }\left(t:I\right)$ 为当出发时间 $t\in I$ 时所有受影响区间点的集合。特别地，当删除故障边 $\left(v_x,v_y\right)\left(t:I\right)$ 后，若 $SP\left(t:I\right)$ 中不存在以 $v_y\left(t:I\right)$ 为头节点的边，则点 $v_y\left(t:I\right)$ 本身也是一个受影响区间点。

由于路径的重建首要考虑范围为在相应时间段内的受影响区域，所以用 ${\left|\delta \right|}_t$ 表示路径所有出发时间区间内受影响区间点数目的最大值，用 ${\Vert \delta \Vert }_t$ 表示所有出发时间区间内受影响区间点和受影响区间边总数的最大值。

3.2. 主要算法和实现

3.2.1. 算法描述

由于本文的主要工作是在时变情形下修复最短路径，因此本文将故障发生前的最短路 $P^{*}\left(t\right)$ 及每个点对应的 $l_{v_i}^{*}\left(t\right)$ 作为一个输入，其中 $v_i\in V\left(G\right)$，该输入可由文献 [17] 中TIP算法直接得到，且该算法输出时间段I的一个完全划分 $I_1,I_2,\cdots ,I_h$，对每一个 $I_i\left(i=1,\cdots ,h\right)$，当出发时刻 $t\in I_i$ 时得到了最短 $v_s{v}_d$ -路 $P_i^{*}\left(t:I_i\right)$ 和最短旅行时间函数 $w_{v_s{v}_d}^{*}\left(t:I_i\right)$，由此可得到最早到达时间函数 $l_{v_d}^{*}\left(t:I_i\right)$。

在算法1中，首先对所有点 $v_i\in V\left(G\right)$，初始化 $l_{v_i}\left(t\right)=l_{v_i}^{*}\left(t\right)$ 以便更新到达时间函数(第1行)，由于算法中给定的故障为 $\mathcal{F}=\left[\left(v_x,v_y\right),L\right]$，其中 $L=\left[t^{\prime },t^{″}\right]$，因此首先根据故障时间段 $\left[t^{\prime },t^{″}\right]$ 以及故障边 $\left(v_x,v_y\right)$ 确定故障出发时间区间子集 $\left\{\overline{I_k}\right\}$ (第2行)。这里，根据故障确定出发时间区间子集时， $l_{v_y}^{*}\left(t\right)$ 需要同时满足以下两个条件：

1) $l_{v_y}^{*}\left(t\right)\in \left(t^{\prime }+w_{\left(v_x,v_y\right)}\left(l_{v_x}^{*}\left(t\right)\right),t^{″}+w_{\left(v_x,v_y\right)}\left(l_{v_x}^{*}\left(t\right)\right)\right)$

2) $l_{v_y}^{*}\left(t\right)\in \left(t^{\prime },t^{″}\right)$

综合以上两式，得 $l_{v_y}^{*}\left(t\right)\in \left(t^{\prime },t^{″}+w_{\left(v_x,v_y\right)}\left(l_{v_x}^{*}\left(t\right)\right)\right)$，若将该函数值范围对应的自变量区间子集记为 $\left\{\overline{I_k}\right\}$，则 $\left\{\overline{I_k}\right\}$ 为故障对应的出发时间区间子集(第2行)。

而对于任意点 $v_i\in V\left(G\right)$，由于 $l_{v_i}^{*}\left(t\right)$ 和 $P_{v_1{v}_i}^{*}\left(t\right)$ 都是已知的，因此只要将所有点的最早到达时间函数根据出发时间区间段再次统一分段就可得到不同时间段的最短路子图(第3行) (参考例1)，并且每一个最短路子图都记录了 $l_{v_i}^{*}\left(t\right)$ 和 $P_{v_1{v}_i}^{*}\left(t\right)$ -路。这样，当某条边在某个时间段发生故障时，只需要选择受故障影响的部分最短路子图进行相应修复即可，即只需要更新受影响区域，而无需对整个最短路子图都进行修复，简化了算法过程。基于此，本文给出解决方案，见算法1。

例1：假设给定时变网络图 $G\left(V,E,W,T\right)$，见下图1，其中图(a)是图结构 $\left(V\left(G\right),E\left(G\right)\right)$，共包含4个顶点5条边，其中 $V\left(G\right)=\left\{v_1,v_2,v_3,v_4\right\}$， $v_1$ 为源点， $v_4$ 为汇点，令 $\overline{I_k}=T=\left[0,6\right]$。边

$\left(v_1,v_2\right),\left(v_1,v_3\right),\left(v_2,v_3\right),\left(v_2,v_4\right),\left(v_3,v_4\right)$ 的旅行时间函数 $w_{\left(v_1,v_2\right)}\left(t\right),w_{\left(v_1,v_3\right)}\left(t\right),w_{\left(v_2,v_3\right)}\left(t\right),w_{\left(v_2,v_4\right)}\left(t\right),w_{\left(v_3,v_4\right)}\left(t\right)$ 分别见图(b)~(f)，下面给出当 $t\in \overline{I_k}$ 时求取最短路子图 $SP\left(t:\overline{I_k}\right)$ 的步骤。

(a) $\left(V\left(G\right),E\left(G\right)\right)$(b) $w_{\left(v_1,v_2\right)}\left(t\right)$(c) $w_{\left(v_1,v_3\right)}(\; t\; )$

(d) $w_{\left(v_2,v_3\right)}\left(t\right)$(e) $w_{\left(v_2,v_4\right)}\left(t\right)$(f) $w_{\left(v_3,v_4\right)}(\; t\; )$

Figure 1. Time varying network graph $G\left(V,E,W,T\right)$

图1. 时变网络图 $G\left(V,E,W,T\right)$

首先利用 算法可以得到各个点的最早到达时间函数如下：

$l_{v_1}^{*}\left(t\right)=t,t\in \left[0,6\right].$

$l_{v_2}^{*}\left(t\right)=t+1,t\in \left[0,6\right].$

$l_{v_3}^{*}\left(t\right)=\{\begin{array}{ll}t+0.5,\hfill & t\in \left[0,0.5\right);\hfill \\ 5t-1.5,\hfill & t\in \left[0.5,0.875\right);\hfill \\ t+2,\hfill & t\in \left[0.875,6\right].\hfill \end{array}$

$l_{v_4}^{*}\left(t\right)=\{\begin{array}{ll}t+3.5,\hfill & t\in \left[0,1.375\right);\hfill \\ 0.2t+4.6,\hfill & t\in \left[1.375,4\right);\hfill \\ t+3,\hfill & t\in \left[4,6\right].\hfill \end{array}$

$P_{v_1{v}_1}^{*}\left(t\right)=\langle v_1\rangle ,t\in \left[0,6\right].$

$P_{v_1{v}_2}^{*}\left(t\right)=\langle v_1,v_2\rangle ,t\in \left[0,6\right].$

$P_{v_1{v}_3}^{*}\left(t\right)=\{\begin{array}{ll}\langle v_1,v_3\rangle ,\hfill & t\in \left[0,0.5\right);\hfill \\ \langle v_1,v_3\rangle ,\hfill & t\in \left[0.5,0.875\right);\hfill \\ \langle v_1,v_2,v_3\rangle ,\hfill & t\in \left[0.875,6\right].\hfill \end{array}=\{\begin{array}{ll}\langle v_1,v_3\rangle ,\hfill & t\in \left[0,0.875\right);\hfill \\ \langle v_1,v_2,v_3\rangle ,\hfill & t\in \left[0.875,6\right].\hfill \end{array}$

$P_{v_1{v}_4}^{*}\left(t\right)=\{\begin{array}{ll}\langle v_1,v_2,v_4\rangle ,\hfill & t\in \left[0,1.375\right);\hfill \\ \langle v_1,v_2,v_3,v_4\rangle ,\hfill & t\in \left[1.375,4\right);\hfill \\ \langle v_1,v_2,v_3,v_4\rangle ,\hfill & t\in \left[4,6\right].\hfill \end{array}=\{\begin{array}{ll}\langle v_1,v_2,v_4\rangle ,\hfill & t\in \left[0,1.375\right);\hfill \\ \langle v_1,v_2,v_3,v_4\rangle ,\hfill & t\in \left[1.375,6\right].\hfill \end{array}$

则当 $t\in \overline{I_k}=T=\left[0,6\right]$ 时，最短路子图 $SP\left(t:\overline{I_k}\right)$ 为：

$\begin{array}{c}SP\left(t:\left[0,6\right]\right)=\{\begin{array}{ll}\left(v_1,v_2\right),\left(v_1,v_3\right),\left(v_2,v_4\right),\hfill & t\in \left[0,0.5\right);\hfill \\ \left(v_1,v_2\right),\left(v_1,v_3\right),\left(v_2,v_4\right),\hfill & t\in \left[0.5,0.875\right);\hfill \\ \left(v_1,v_2\right),\left(v_2,v_3\right),\left(v_2,v_4\right),\hfill & t\in \left[0.875,1.375\right);\hfill \\ \left(v_1,v_2\right),\left(v_2,v_3\right),\left(v_3,v_4\right),\hfill & t\in \left[1.375,4\right);\hfill \\ \left(v_1,v_2\right),\left(v_2,v_3\right),\left(v_3,v_4\right),\hfill & t\in \left[4,6\right].\hfill \end{array}\\ =\{\begin{array}{ll}\left(v_1,v_2\right),\left(v_1,v_3\right),\left(v_2,v_4\right),\hfill & t\in \left[0,0.875\right);\hfill \\ \left(v_1,v_2\right),\left(v_2,v_3\right),\left(v_2,v_4\right),\hfill & t\in \left[0.875,1.375\right);\hfill \\ \left(v_1,v_2\right),\left(v_2,v_3\right),\left(v_3,v_4\right),\hfill & t\in \left[1.375,6\right].\hfill \end{array}\end{array}$

令 $\mathcal{J}=\left\{\left[0,0.875\right),\left[0.875,1.375\right),\left[1.375,6\right]\right\}$，则 $\mathcal{J}$ 是时间区间 $T=\left[0,6\right]$ 的最大子集集合，且满足所有点 $v_i\in V\left(G\right)$ 在每一个 $\mathcal{J}$ 的子集中都在同一个最短路子图中。

在上述实例中，最短路子图有3个，而我们的算法中，由于时变网络的不确定性，将最短路子图的个数记为 $\alpha \left(T\right)$。

选出故障出发时间区间后确定对应的最短路子图 $\left\{SP\left(t:\overline{I_k}\right)\right\}$ 后(第3行)，这就意味着算法只需要对选出的 $\left\{\overline{I_k}\right\}$ 区间依次遍历。由于故障边是 $\left(v_x,v_y\right)\left(t:\overline{I_k}\right)$，因此，对于每一个区间 $\overline{I_k}$，应首先将边 $\left(v_x,v_y\right)$ 从 $SP\left(t:\overline{I_k}\right)$ 中删除(第5行)并减小 $v_y\left(t:\overline{I_k}\right)$ 的入度值 ${\delta }^{-}\left(v_y\left(t:\overline{I_k}\right)\right)$ (第6行)，再判断 $v_y\left(t:I\right)$ 在当前最短路子图中的入度值。若删边之后入度值为0，说明 $v_y\left(t:\overline{I_k}\right)$ 的最早到达时间函数需要更新，即 $v_y\left(t:\overline{I_k}\right)$ 此时是一个受影响区间点(第7行)。

因此，当给定 $l_{v_i}^{*}\left(t:\overline{I_k}\right)$ 、 $SP\left(t:\overline{I_k}\right)$ 时，假设故障 $\mathcal{F}=\left(\left(v_x,v_y\right),L\right)$，则会出现以下两种情况：

Case 1. $\left(v_x,v_y\right)\in SP\left(t:\overline{I_k}\right)$ 且 ${\delta }^{-}\left(v_y\left(t:\overline{I_k}\right)\right)=1$

说明故障边的出现导致 $l_{v_i}^{*}\left(t\right)$ 和 $SP\left(t\right)$ 都需要进行更新，即算法的主要部分；

Case 2. $\left(v_x,v_y\right)\notin SP\left(t:\overline{I_k}\right)$ 或 ${\delta }^{-}\left(v_y\left(t:\overline{I_k}\right)\right)>1$

说明故障时间段对初始最优路没有影响，无需对最短路子图更新，直接删除故障边。

接下来，针对Case 1给出更新最早到达时间函数的算法，主要分为两个子算法：

算法2：通过故障识别受影响区间点和受影响区间边

当出发时刻 $t\in \overline{I_k}$ 时，由于故障边为 $\left(v_x,v_y\right)$，因此 $\left(v_x,v_y\right)\left(t:\overline{I_k}\right)$ 是受影响区间边。当从 $SP\left(t:\overline{I_k}\right)$ 中删除边 $\left(v_x,v_y\right)$ 后点 $v_y$ 的入度大于1，说明不需要更新解，但当点 $v_y$ 的入度为0，则说明点 $v_y\left(t:\overline{I_k}\right)$ 是受影响区间点，因此初始化工作点集 $J=\left\{v_y\left(t:\overline{I_k}\right)\right\}$，受影响点集 $V_{\delta }\left(t:\overline{I_k}\right)=\varnothing$ (第1~2行)。这里， $v_i\left(t:\overline{I_k}\right)$ 被称作区间点，表示当出发时刻 $t\in \overline{I_k}$ 时考虑点 $v_i$。其中，工作点集J中存储一些已经识别为受影响区间点但并未进行处理的点。初始J中只有 $v_y\left(t:\overline{I_k}\right)$，因此在后续的算法过程中，从 $v_y\left(t:\overline{I_k}\right)$ 开始依次处理J中的点(第3~14行)。而每次当点 $v_i\left(t:\overline{I_k}\right)\in J$ 被处理完之后，相应地将 $v_i\left(t:\overline{I_k}\right)$ 从J中移除，并将以 $v_i$ 为头节点的 $SP\left(t:\overline{I_k}\right)$ 边都删除(受影响区间边) (第4~5行)。依次进行这样的迭代直到得到区间 $\overline{I_k}$ 内的完整受影响区间点集 $V_{\delta }\left(t:\overline{I_k}\right)$。

算法3：更新受影响区间点的最早到达函数和最短路子图

算法3主要利用了Dijkstra优先搜索思想来更新受影响区间点的最早到达时间函数。由于本文考虑的最短路子图是从源点到其它所有点的最短路，因此当已知任意区间点 $v_i\left(t:\overline{I_k}\right)$ 更新前的最早到达时间函数 $l_{v_i}^{*}\left(t:\overline{I_k}\right)$ 时，我们可以运用已知的最早到达时间函数和最短路子图的结构来更新受影响区间点的最早到达时间函数 ${l^{\prime }}_{v_i}\left(t:\overline{I_k}\right)$。

算法3用到的两个主要步骤：

1) 根据不受影响区间点的最早到达时间函数更新受影响区间点的最早到达时间函数(考虑前向边) (第2~10行)

2) 考虑受影响区间点发出的边导致的最早到达时间函数(考虑后向边) (第11~23行)

步骤1的主要思想参考下图2故障边删除模型，A、B分别代表在区间 $\overline{I_k}$ 内的不受影响区间点集 $\overline{V_{\delta }}\left(t:\overline{I_k}\right)$ 和受影响区间点集 $V_{\delta }\left(t:\overline{I_k}\right)$， $\left(v_x,v_y\right)\left(t:\overline{I_k}\right)$ 是受影响区间边， $v_y\left(t:\overline{I_k}\right)\in V_{\delta }\left(t:\overline{I_k}\right)$，

$v_x\left(t:\overline{I_k}\right)\in \overline{V_{\delta }}\left(t:\overline{I_k}\right)$， $v_a\left(t:\overline{I_k}\right)\in \overline{V_{\delta }}\left(t:\overline{I_k}\right)$。当 $t\in \overline{I_k}$ 时，由于对于任意点 $v_x\left(t:\overline{I_k}\right)\in \overline{V_{\delta }}\left(t:\overline{I_k}\right)$， $l_{v_x}^{*}\left(t:I_k\right)$ 是已知的且不需要更新，因此当 $v_y\left(t:\overline{I_k}\right)\in V_{\delta }\left(t:\overline{I_k}\right)$ 时，假设当 $t\in \overline{I_k}$ 时初始的最优 $v_s{v}_y$ -路经过边 $\left(v_x,v_y\right)$，且点 $v_y\left(t:\overline{I_k}\right)$ 的最早到达时间函数 $l_{v_y}^{*}\left(t:I_k\right)=l_{v_x}^{*}\left(t:I_k\right)+w_{\left(v_x,v_y\right)}\left(l_{v_x}^{*}\left(t:I_k\right)\right)$。假设对于点 $v_y\left(t:\overline{I_k}\right)$，当 $I_k\subseteq \overline{I_k}$ 时，此时找到的当前最优不受影响的前继点为 $v_a\left(t:I_k\right)$，则更新新的 $v_s{v}_y$ -路，此时该条路经过边 $\left(v_a,v_y\right)$，且新的 $l_{v_y}\left(t:I_k\right)=l_{v_a}^{*}\left(t:I_k\right)+w_{\left(v_a,v_y\right)}\left(l_{v_a}^{*}\left(t:I_k\right)\right)$。这样，通过这种思想就可以初步更新受影响区间点的最早到达时间函数。因此，对于每个受影响区间点 $v_b\left(t:\overline{I_k}\right)$，依次选取最优的不受影响区间点 $\left\{v_a\left(t:I_k\right)\right\}$，其中 $I_k\subseteq \overline{I_k}$，且 $\left\{I_k\right\}$ 是 $\overline{I_k}$ 的完全划分(第3行)，并将边 $\left\{\left(v_a,v_b\right)\left(t:I_k\right)\right\}$ 加入到 $\left\{SP\left(t:I_k\right)\right\}$ 中(第4行)。最后，将更新过的区间点 $v_b\left(t:I_k\right)$ 放入Q中并更新 $\left\{v_b\left(t:I_k\right)\right\}$ 的最早到达时间函数(第5~9行)。

Figure 2. Fault edge deletion model

图2. 故障边删除模型

在步骤2中(第11~23行)，对于每一个受影响区间点 $v_i\left(t:I_k\right)\in Q$，在第2~10行已经根据不受影响区间点集中的最早到达时间函数进行了初步更新。因此，在此步骤中，首先根据这些点的最早到达时间函数选取每个区间 ${I^{\prime }}_k$ 中值最小的点，将选出的这些区间点记为 $\left\{v_b\left(t:{I^{\prime }}_k\right)\right\}$，其中 ${I^{\prime }}_k\subseteq I_k$，且 $\left\{{I^{\prime }}_k\right\}$ 是 $I_k$ 的完全划分。这就说明 $\left\{v_b\left(t:{I^{\prime }}_k\right)\right\}$ 已是最优区间点，之后无需再进行更新，因此从Q中取出(第13行)。而对于选出的区间点 $\left\{v_b\left(t:{I^{\prime }}_k\right)\right\}$，由于本文修复的是最短路子图，因此首先根据前继点判断入度是否为非0，即是否在 ${I^{″}}_k\subseteq {I^{\prime }}_k$ 中存在不同的 $v_s{v}_b$ -路但具有相同的到达时间(第15~17行)。最后，根据已经选出的最优区间点 $\left\{v_b\left(t:{I^{\prime }}_k\right)\right\}$ 更新后继点的最早到达时间函数(第18~21行)，继续迭代直到Q中的元素为空。步骤2的主要思想是Dijkstra优先搜索，每次选取当前最早到达的点进行向后探搜索，直到所有的受影响区间点都被遍历完。

在算法1中，第2行 $\arg \min \left\{l_{v_y}^{*}\left(t\right)|l_{v_y}^{*}\left(t\right)\in \left(t^{\prime },t^{″}+w_{\left(v_x,v_y\right)}\left(l_{v_x}^{*}\left(t\right)\right)\right)\right\}$ 表示返回值函数

$\left\{l_{v_y}^{*}\left(t\right)|l_{v_y}^{*}\left(t\right)\in \left(t^{\prime },t^{″}+w_{\left(v_x,v_y\right)}\left(l_{v_x}^{*}\left(t\right)\right)\right)\right\}$ 对应的自变量区间，即出发时间区间。第12行

$\left\{v_b\left(t:{I^{\prime }}_k\right)\right\}=\arg \min \left\{l_{v_i}\left(t:I_k\right)|v_i\left(t:I_k\right)\in Q\right\}$ 表示返回在Q中具有最早到达时间函数的区间点集合

$\left\{v_b\left(t:{I^{\prime }}_k\right)\right\}$，这里 $\left\{{I^{\prime }}_k\right\}$ 是 $I_k$ 的完全划分，复杂度为 $O\left(\alpha \left(T\right)\log n\right)$，其中n为Q中元素的个数， $\alpha \left(T\right)$ 是每个函数操作所需的时间代价，参考例2。算法2中第7行 $\text{Insert}\left(Q,v_b\left(t:I_k\right),l_{v_b}\left(t:I_k\right)\right)$ 表示如果 $v_b\left(t:I_k\right)$ 在Q中，则更新 $l_{v_b}\left(t:I_k\right)$，如果不在Q中，将 $v_b\left(t:I_k\right)$ 以及对应的最早到达时间函数 $l_{v_b}\left(t:I_k\right)$ 放入 中，第20行 $\text{Update}\left(Q,v_c\left(t:{I^{″}}_k\right),l_{v_c}\left(t:{I^{″}}_k\right)\right)$ 则表示更新Q中 $v_c\left(t:{I^{″}}_k\right)$ 对应的最早到达时间函数 $l_{v_c}\left(t:{I^{″}}_k\right)$。

例2：argmin解释：设 $T=\left[0,3\right]$，且

$l_{v_1}\left(t:T\right)=2,t\in \left[0,3\right].$

$l_{v_2}\left(t:T\right)=\{\begin{array}{ll}t+1,\hfill & t\in \left[0,2\right);\hfill \\ 3,\hfill & t\in \left[2,3\right].\hfill \end{array}$

则：

$\arg \min \left\{l_{v_1}\left(t:\left[0,3\right]\right),l_{v_2}\left(t:\left[0,3\right]\right)\right\}=\{\begin{array}{l}{v}_2\left(t:\left[0,1\right)\right);\\ v_1\left(t:\left[1,3\right]\right).\end{array}$

令 $\mathcal{J}=\left\{\left[0,1\right),\left[1,3\right]\right\}$，则 $\mathcal{J}$ 是时间区间 $T=\overline{I_k}=\left[0,3\right]$ 的最小子集合，且满足在每一个子区间内仅存在一个点 $v_i$ 使得 $v_i\left(t:T\right)=\arg \min \left\{l_{v_i}\left(t:T\right)\right\}$。

3.2.2. 算法方案

本节中，算法1针对本文问题给出了主要算法方案，算法详细描述参考3.3.1。

接下来，算法2根据最短路子图给出识别受影响区间点以及删除受影响区间边的算法方案。

最后，算法3给出了更新最早到达时间函数的算法实现方案。

4. 算法正确性分析

为方便描述，后续的证明均以出发时刻 $t\in I_k$ 的情况进行说明，其中这里的 $I_k$ 表示任意出发时间区间。另外，再次需要强调的是，当 $t\in I_k$ 时，对任意点 $v_i\in V\left(G\right)$， $l_{v_i}^{*}\left(t:I_k\right)$ 、 $l_{v_i}\left(t:I_k\right)$ 和 ${l^{\prime }}_{v_i}\left(t:I_k\right)$ 分别表示更新前、更新过程中和更新后的最早到达时间函数。

观察：在更新最早到达时间函数操作之前，以下的两个性质是成立的：

1) 对于任意点 $v_i\in V\left(G\right)$ 及 $t\in I_k$，从 $v_s$ 到 $v_i$ 的最早到达时间函数被正确存储，即 $l_{v_i}\left(t:I_k\right)=l_{v_i}^{*}\left(t:I_k\right)$。

2) $SP\left(t:I_k\right)$ 是当 $t\in I_k$ 时以源点 $v_s$ 为源节点的最短路子图，即对于任意点 $v_i\in V\left(G\right)$ 及 $t\in I_k$，在 $SP\left(t:I_k\right)$ 中从 $v_s$ 到 $v_i$ 的路就是最短路。

为了证明算法的正确性，我们将说明在算法执行完后上面两个性质仍然成立。

引理4.1 $G\left(V,E,W,T\right)$ 为给定时变网络图，如果删边操作在边 $\left(v_x,v_y\right)$ 上执行，且性质1、2成立，则对任意出发时间 $t\in I_k$，算法2正确处理了所有点。

下面我们将证明更新算法(即算法3)的正确性。

引理4.2 给定时变网络图 $G\left(V,E,W,T\right)$，如果删边操作在边 $\left(v_x,v_y\right)$ 上执行，当出发时间 $t\in I_k$ 时，则该算法对任意区间点 $v_i\left(t:I_k\right)\in Q$ 正确地以非递减顺序计算了 $l_{v_i}\left(t:I_k\right)$。

证明：对于任意点 $v_i\left(t:I_k\right)\in Q$，假设点 $v_j\left(t:I_k\right)$ 为从Q中取出不满足非递减顺序的第一个点(算法3第12行)。令当 $t\in I_k$ 时从Q中先取出 $v_i$ 再取出 $v_j$，由假设可知， $l_{v_j}\left(t:I_k\right)<l_{v_i}\left(t:I_k\right)$。当 $v_j$ 从Q中取出时， $l_{v_j}\left(t:I_k\right)$ 已经被计算过(算法2第3行)，即 $l_{v_j}\left(t:I_k\right)=l_{v_a}^{*}\left(t:I_k\right)+w_{\left(v_a,v_j\right)}\left(l_{v_a}^{*}\left(t:I_k\right)\right)$，其中 $v_j$ 满足 $l_{v_j}\left(t:I_k\right)=l_{v_a}\left(t:I_k\right)+w_{\left(v_a,v_j\right)}\left(l_{v_a}\left(t:I_k\right)\right)>l_{v_a}\left(t:I_k\right)=l_{v_a}^{*}\left(t:I_k\right)$。因此， $l_{v_a}\left(t:I_k\right)<l_{v_j}\left(t:I_k\right)<l_{v_i}\left(t:I_k\right)$。由算法3第12行的取点规则可知，点 $v_a$ 比点 $v_j$ 先从Q中取出，且 $v_j$ 的优先性和最早到达时间函数被正确更新(算法3第20行)，且 $v_j$ 的更新在点 $v_i$ 之前，但这与假设矛盾，因此假设不成立。

引理4.3 给定时变网络图为 $G\left(V,E,W,T\right)$，如果删边操作在边 $\left(v_x,v_y\right)$ 上执行，且性质1、2成立，则算法3执行完毕之后性质1、2仍然成立。

证明：引理4.1首先说明了算法2正确处理了所有点。接下来，对于任意受影响区间点 $v_b\in V_{\delta }\left(t:I_k\right)$，执行第算法2第2~10行，由于点 $v_a$ 在 $I_k$ 区间内是不受影响区间点，因此该操作保证了 $v_i\left(t:I_k\right)$ 在所有区间的当前最优前继点 $v_a$ 被选出，并将此时的 $l_{v_i}\left(t:I_k\right)$ 记录下来供后续步骤使用。现在说明对于满足算法3中第15行和第18行条件的点，在算法3执行完毕之后性质1、2仍然成立。

对于满足算法3中满足15行条件的任意点 $v_i$，根据引理4.2可得 $l_{v_a}^{*}\left(t:I_k\right)={l^{\prime }}_{v_a}\left(t:I_k\right)$，又由于 $l_{v_b}\left(t:I_k\right)={l^{\prime }}_{v_b}\left(t:I_k\right)=l_{v_b}^{*}\left(t:I_k\right)$，因此 $v_b\left(t:I_k\right)$ 的到达时间在第38行不会被增加，因此，对于满足条件第38行的任意点 $v_b$，性质1、2成立。

为了证明满足算法3中第18行条件的点 $v_b$ 在算法3执行完毕之后性质1、2仍然成立，即 $l_{v_b}\left(t:I_k\right)={l^{\prime }}_{v_b}\left(t:I_k\right)$，下面我们分别证明 $l_{v_b}\left(t:I_k\right)\ge {l^{\prime }}_{v_b}\left(t:I_k\right)$ 和 $l_{v_b}\left(t:I_k\right)\le {l^{\prime }}_{v_b}\left(t:I_k\right)$。

要证明 $l_{v_b}\left(t:I_k\right)\ge {l^{\prime }}_{v_b}\left(t:I_k\right)$，首先证明如下断言成立：

断言：在算法3的执行过程中，当点 $v_b$ 的到达时间函数不是无穷大时(算法3第6行)， $v_b$ 的优先性就是在删边之后的图中从源点到点 $v_b$ 的最早到达时间函数。

证明：首先，在算法2中，当区间点 $v_b\left(t:I_k\right)$ 被插入到Q中时，它的优先性是

$l_{v_a}\left(t:I_k\right)+w_{\left(v_a,v_b\right)}\left(l_{v_a}\left(t:I_k\right)\right)=l_{v_a}^{*}\left(t:I_k\right)+w_{\left(v_a,v_b\right)}\left(l_{v_a}^{*}\left(t:I_k\right)\right)\ge {l^{\prime }}_{v_b}\left(t:I_k\right)$，其中 $v_a\left(t:I_k\right)$ 是满足第3行条件的 $v_b\left(t:I_k\right)$ 最优的不受影响邻居区间点且 ${l^{\prime }}_{v_a}\left(t:I_k\right)=l_{v_a}^{*}\left(t:I_k\right)$。 $v_b\left(t:I_k\right)$ 的优先性对应于在删边之后的 $SP\left(t:I_k\right)$ 子图中从 $v_s$ 到 $v_b$ 的最早到达时间函数。这就说明在算法2结束后我们的陈述仍然是正确的。

假设我们给出的断言在算法3的执行中不正确。设 $v_b\left(t:I_k\right)$ 是在Q中使得陈述不正确的具有最小优先性的点， $l_{v_b}\left(t:I_k\right)=l_{v_a}\left(t:I_k\right)+w_{\left(v_a,v_b\right)}\left(l_{v_a}\left(t:I_k\right)\right)$。由于我们假设断言不正确，即 $l_{v_b}\left(t:I_k\right)$ 不是在删边之后的 $SP\left(t:I_k\right)$ 子图中从源点 $v_s$ 到 $v_b$ 的最早到达时间函数，即 $l_{v_b}\left(t:I_k\right)<{l^{\prime }}_{v_b}\left(t:I_k\right)$。由于该陈述对于区间点 $v_b\left(t:I_k\right)$ 在算法3开始的时候是正确的，这就意味着在Q中 $v_b\left(t:I_k\right)$ 的优先性已经改变为 $l_{v_a}\left(t:I_k\right)+w_{\left(v_a,v_b\right)}\left(l_{v_a}\left(t:I_k\right)\right)$ (第3行)。通过假设，当点 $v_a$ 从Q中取出， $l_{v_b}\left(t:I_k\right)$ 就是在删边之后的新图中从源点从 $v_s$ 到 $v_b$ 的最早到达时间函数。这与假设矛盾，所以断言成立。下面只需证明 $l_{v_b}\left(t:I_k\right)\le {l^{\prime }}_{v_b}\left(t:I_k\right)$。

假设 $v_b\left(t:I_k\right)$ 是第一个从Q中取出来但 $l_{v_b}\left(t:I_k\right)$ 不是最优的点，也就是 $l_{v_b}\left(t:I_k\right)>{l^{\prime }}_{v_b}\left(t:I_k\right)$。令 $v_a\left(t:I_k\right)$ 是 $v_b\left(t:I_k\right)$ 在 $SP\left(t:I_k\right)$ 中的父节点，其中点 $v_a\left(t:I_k\right)$ 被正确处理，即

${l^{\prime }}_{v_b}\left(t:I_k\right)={l^{\prime }}_{v_a}\left(t:I_k\right)+w_{\left(v_a,v_b\right)}\left({l^{\prime }}_{v_a}\left(t:I_k\right)\right)$。通过引理4.2及 ${l^{\prime }}_{v_a}\left(t:I_k\right)<{l^{\prime }}_{v_b}\left(t:I_k\right)$，我们推得：当 $v_a$ 满足第18行时，由于 $v_b$ 是第一个满足 $l_{v_a}^{*}\left(t:I_k\right)={l^{\prime }}_{v_a}\left(t:I_k\right)$， $l_{v_b}\left(t:I_k\right)>l_{v_a}\left(t:I_k\right)+w_{\left(v_a,v_b\right)}\left(l_{v_a}\left(t:I_k\right)\right)={l^{\prime }}_{v_b}\left(t:I_k\right)$ 的点，这说明 $v_a\left(t:I_k\right)$ 优先 $v_b\left(t:I_k\right)$ 从Q中取出。另外，当 $l_{v_a}\left(t:I_k\right)$ 被正确计算之后，第18行就考虑边 $\left(v_a,v_b\right)$，且更新 $v_b$ 的最早到达时间函数 $l_{v_b}\left(t:I_k\right)$ 为 $l_{v_a}\left(t:I_k\right)+w_{\left(v_a,v_b\right)}\left(l_{v_a}\left(t:I_k\right)\right)$ (第18行)。这与 $l_{v_b}\left(t:I_k\right)$ 不是最优矛盾。

因此，该引理得证。

5. 算法复杂性分析

边权增加的修复最短路(即增量算法)最坏情况下运行时间为 $O\left(\Vert \delta \Vert +\left|\delta \right|\log \left|\delta \right|\right)$。其中 $\left|\delta \right|$ 表示受影响区间点的数目， $\Vert \delta \Vert$ 表示受影响区间点和受影响区间边的总数，该复杂度分析见 [12]。基于这种自适应参数的思想，下面给出本文中算法的复杂度分析。

在算法1中，第1~3行的运行时间为 $O\left(1\right)$，由于在本文中，故障的出发时间区间集为 $\left\{\overline{I_k}\right\}$，对于每个区间 $\overline{I_k}$，我们令 $\max \left|V_{\delta }\left(t:\overline{I_k}\right)\right|={\left|\delta \right|}_t$，表示所有出发时间区间内受影响区间点数目的最大值，相应地， ${\Vert \delta \Vert }_t$ 表示所有出发时间区间内受影响区间点和受影响区间边总数的最大值。第3行的for循环最多执行 $\alpha \left(T\right)$ 次，下面分析算法2和算法3的复杂度。

在算法2中，第3行的while循环最多执行 ${\left|\delta \right|}_t$ 次，而第8行的for循环最多执行 $\left|succ\left(v_b\right)\right|$ 次，其余操作的复杂度均为 $O\left(1\right)$，因此算法2的总复杂度为 $O\left({\displaystyle {\sum }_{v_b\in V_{\delta }\left(t:\overline{I_k}\right)}\left|succ\left(v_b\right)\right|}\right)=O\left({\Vert \delta \Vert }_t\right)$，其中 ${\Vert \delta \Vert }_t$ 表示所有出发时间区间内受影响区间点和受影响区间边总数的最大值。在算法3中，第2行最多执行 ${\left|\delta \right|}_t$ 次，第3行最多执行 $\log \left(prec\left(v_b\right)\right)$ 次，由于 $prec\left(v_b\right)$ 为常数，故时间复杂度为 $O\left(1\right)$。第11行最多执行 ${\left|\delta \right|}_t$ 次，第12行的操作复杂度为 $O\left(\log {\left|\delta \right|}_t\right)$，因此算法3的总复杂度为： ${\left|\delta \right|}_t\cdot \log {\left|\delta \right|}_t$。

故该算法的总复杂度为： $O\left(\alpha \left(T\right)\cdot \left[{\Vert \delta \Vert }_t+{\left|\delta \right|}_t\cdot \log {\left|\delta \right|}_t\right]\right)$。

由此可见，在大规模的时变网络中，当故障影响范围较小或者故障持续时间较短时，本文提出的算法具有较优的复杂性。

6. 结语

本文研究了单链路故障情形下找时变的故障修复最短路径问题，当给定任意链路故障 之后，本文基于原始的时变最短路径进行修复进而找到新的时变最短路径，以保证网络的生存性和服务质量要求。针对该问题，本文给出一个灵活且高效的算法解决该问题，该算法不仅利用了最短路子图的思想和自适应参数降低了计算复杂度，而且在路径修复过程中有效利用了时间段划分并保证了节点之间传输的连续性，最后证明了该算法的正确性并计算得到该算法的时间复杂度为 $O\left(\alpha \left(T\right)\cdot \left[{\Vert \delta \Vert }_t+{\left|\delta \right|}_t\cdot \log {\left|\delta \right|}_t\right]\right)$，其中 ${\left|\delta \right|}_t=\max \left|V_{\delta }\left(t:\overline{I_k}\right)\right|$，表示所有出发时间区间内受影响区间点数目的最大值， ${\Vert \delta \Vert }_t$ 表示所有出发时间区间内受影响区间点和受影响区间边总数的最大值， $\alpha \left(T\right)$ 是每个函数操作所需的时间代价。