# Journey Planning Algorithms for Massive Delay-Prone Transit Networks +
## 5 Dynamic Public Transit Labeling
Moreover, for any \(h\in\textsc{c}_{out}(v)\) the path between \(v\) and \(h\) must pass through at least a vertex in \(\textsc{right}_{x}\). This implies that, if we have the set of vertices \(S=\{v\in V\,|\,v\
otin\textsc{left}_{x}\land\exists u\in N_{in}^{G^{\prime}}( u)\,:\,u\in\textsc{left}_{x}\right\}\), that are reachable from \(v\) in \(G^{\prime}\), then \(d_{G^{\prime}}(v,h)\) is given by the minimum value between \(\delta_{vu}+\textsc{query}(u,h,\textsc{L})\) among all vertices \(u\in S\) (note that \(\delta_{vu}\) can be retrieved from \(\textsc{L}\)). Therefore, to compute \(d_{G^{\prime}}(v,h)\) for all \(h\in\textsc{c}_{out}(v)\), we run a pruned BFS starting from \(v\) (see sub-routine shown in Algorithm 8). ```
Input: Directed acyclic graph \(G\), a vertex \(s\) of \(G\), sets \(\textsc{right}_{x}\) and \(\textsc{left}_{x}\) Output: Set of pairs of vertices and relative distances from \(s\)
1\(Q\leftarrow\emptyset\) ;
2\(A_{s}\leftarrow\emptyset\);
3 foreach\(u\in V\)do
4\(\textsc{visit}[u]\gets 0\);
5\(Q.insert(s,0)\);
6\(\textsc{visit}[s]\gets 1\);
7 while\(Q\
eq\emptyset\)do
8\((u,\delta_{vu})\gets Q.extractMin()\);
9\(\textsc{visit}[u]=2\);
10 if\(u\
otin\textsc{left}_{x}\)then
11\(A_{s}\gets A_{s}\cup\{(u,\delta_{vu})\}\) ;
12
13 else
14 foreach\(v\in N_{out}^{G}(u)\)do
15 if\(\textsc{visit}[v]=0\)then
16\(Q.insert(v,\delta_{vu}+w(u,k))\);
17
18 elseif\(\textsc{visit}[v]=1\)and\(Q.key(v)>\delta_{vu}+w(u,k)\)then
19\(Q.decreaseKey(v,\delta_{vu}+w(u,k))\);
20
21 return\(A_{s}\) // List of pairs of vertices in \(\textsc{right}_{x}\) along with distances from \(s\)
```

**Algorithm 8**Algorithm \(\textsc{customBFS}\). Once all distances are available, we process the vertices in \(\textsc{c}_{out}(v)\) in increasing order with respect to topological sorting. In particular, for each \(w\in\textsc{c}_{out}(v)\) in increasing order of \(t(w)\), we update the label entries by using the computed distances, the notion of superset, and the labeling \(\textsc{L}\) (see Lines 11-21 of Algorithm 9). Whenever we add a new label entry or update an existing one, we _mark_ the entry so that we keep trace of distances that have already been checked. On top of that, after the first iteration, we exploit the marked query every time we need to check whether a discovered distance \(d\), passing through a vertex, is already encoded in the labeling or not. Finally, notice that, whenever we add a new label entry to the 2 hc-sp labeling, we insert it in order to preserve the well-ordered property [26]. This property guarantees that the labeling is minimal in size (i.e., if a single entry is removed, the cover property is broken). To achieve it, vertices are sorted according to any reasonable criterion before the initial preprocessing takes place and, whenever a label entry associated with an hub \(h\) has to be added to the label set of a vertex \(v\), this is done if and only if \(h\) preceedes \(v\) in the established order (we refer the reader to Reference [21; 26] for more details). We denote by \(l(v)\) the position of a vertex \(v\in V\) according to the established order. In particular, it is given by the minimum value we obtain for \(\textsc{query}(w,u,\textsc{L})+\textsc{query}(u,v,\textsc{L})\) among all vertices \(u\in N_{in}^{G^{\prime}}(v)\). If this value is not encoded in the labeling, we add \((u,\delta_{uv})\) to \(\textsc{L}_{in}(v)\) if \(l(v)>l(u)\), otherwise we add \((v,\delta_{uv})\) to \(\textsc{L}_{out}(u)\). We are now ready to discuss on the correctness of the newly proposed approach. **Theorem 4** (Correctness of dag-decpll). : _Let \(G\) be a DAG, let \(\textsc{L}\) be a 2 hc-sp labeling of \(G\), and let \(x\) be a vertex of \(G\). Let \(G^{\prime}=G\setminus\{x\}\) and \(\textsc{L}^{\prime}\) be the output of algorithm dag-decpll when applied to \(G\), \(\textsc{L}\) and \(x\). Then: a) \(G^{\prime}=G\setminus\{x\}\) is a DAG and b) \(\textsc{L}^{\prime}\) is a 2 hc-sp labeling of \(G^{\prime}\)._

Proof. : Concerning (a), the proof is trivial.