# Faster Algorithms for Mining Shortest-Path Distances from Massive Time-Evolving Graphs
## 3 A New Algorithm: queue-2 hc
### recover Phase
In the latter case, the shortest path from \(u\) to \(h\) in  
Figure 6: (a): an example of the contradiction reached in the proof of Lemma 3. Suppose vertex ordering is \(\{x_{0},x_{1},x_{2},\ldots,x_{5}\}\) and all arcs weight 1. Therefore, in any minimal well-ordered \(2\)-hop-cover labeling, entry \((x_{1},\delta_{x_{4}x_{1}}\) cannot belong to \(L_{out}(x_{4})\), due to the pruning test succeeding because of \(x_{0}\). Also, in this case no correct entry is removed by Algorithm clean. (b): restore phase for vertex \(r\). G does not include \((x,y)\) and neither the shortest path from \(h\) to \(v\) in G. Hence, by Lemma 3, correct entries \((h,\delta_{uh})\) and \((h,\delta_{hv})\) must be in \(L^{\prime}_{out}(u)\) and \(L^{\prime}_{in}(v)\), respectively, which implies the pair is covered and the contradiction is reached. **Case (iii)**. : As with case (i), we have that the shortest path in G between \(u\) and \(v\) does not contain \((x,y)\) and that both labels \(L_{out}(u)\) and \(L_{in}(v)\) are not changed by Algorithm 5. Hence, again we have the contradiction of with \(Q(u,v,L)=Q(u,v,L^{\prime})=d_{G}(u,v)=d_{G^{\prime}}(u,v)\). By Property 4 it emerges that to guarantee the property holding for G', it suffices to restart some shortest-path visits as follows. Given a root vertex \(h\in\texttt{IN}\) (\(h\in\texttt{OUT}\)), all vertices \(v\in\texttt{OUT}\) (\(v\in\texttt{IN}\), respectively) are first analyzed in order to find _viable neighbors_ for \(h\). A viable neighbor \(u\in N_{out}(v)\) (\(u\in N_{in}(v)\), respectively) is a neighbor such that: (a) \(h\in L_{out}(u)\) (\(h\in L_{in}(u)\), respectively) and (b) \(u\
ot\in\texttt{OUT}\) (\(u\
ot\in\texttt{IN}\), respectively). For all such neighbors, we know that after the execution of Algorithm clean, there exists at least one shortest path from \(u\) to \(h\) (from \(h\) to \(u\), respectively) that did not contain \((x,y)\) in G. Clearly, there can be many viable neighbors (see Figure 5(b)). Therefore, to correctly discover distances corresponding to shortest paths, the procedure selects the one with a minimum distance encoded in the label entry. In particular, if we call \(\texttt{dmin}=\min\limits_{u\in N_{out}(v),u\
ot\in\texttt{OUT},(h,\delta_{uh })\in L_{out}(u)}[\delta_{uh}+w(v,u)]\) then the algorithm inserts \(v\) into a queue Q with priority dmin (see Algorithm 4). If no viable neighbor exists in G', then the vertex is not inserted in the queue. Observe that the search for viable neighbors can be accelerated by skipping vertices according to their ordering and to the well-ordered property (see lines 5-8 or lines 18-21) that guarantees that if \(v<u\) then \(u\
ot\in L_{in}(v)\) and \(u\
ot\in L_{out}(v)\). ```
Input: Vertex \(v\), neighbor set \(N\), Boolean outgoing, vertex set \(T\). if\(\texttt{OUTGOING}=\texttt{true}\)then
1 foreach\(v_{i}\in N_{in}(v)\) : \(v_{i}\in T\)do
2 if\(\texttt{mark}[v_{i}]\)then
3\(\texttt{mark}[v_{i}]\leftarrow\texttt{true}\);
4\(Q.\texttt{Insert}((v_{i},\delta+w(v_{i},v)))\);
5 elseif\(\delta+w(v_{i},v)<Q.\texttt{key}(v_{i})\)then
6\(Q.\texttt{decreaseKey}((v_{i},\delta+w(v_{i},v)))\);
7
8 else
9 foreach\(v_{i}\in N_{out}(v)\) : \(v_{i}\in T\)do
10 if\(\texttt{mark}[v_{i}]\)then
11\(\texttt{mark}[v_{i}]\leftarrow\texttt{true}\);
12\(Q.\texttt{Insert}((v_{i},\delta+w(v,v_{i})))\);
13 elseif\(\delta+w(v,v_{i})<Q.\texttt{key}(v_{i})\)then
14\(Q.\texttt{decreaseKey}((v_{i},\delta+w(v,v_{i})))\);
```  
**Algorithm 8**Procedure prunedRelax used by Algorithm recover  
Once all vertices in OUT (IN, respectively) has been treated as above, we have that Q contains vertices in OUT (IN, respectively) with at least one viable neighbor, i.e., connected to the vertex h under consideration through a path that is not including \((x,y)\). If Q is empty, it follows that no such vertices exist, and hence it is easy to see that the decremental operation must be an arc removal that has increased the number of strongly connected components of G (otherwise we would have that at least vertex x has vertex \(y\) as viable neighbor).