# Journey Planning Algorithms for Massive Delay-Prone Transit Networks +
## 5 Dynamic Public Transit Labeling
We then perform a linear sweep on both \(\textsc{e-sl}_{out}(i)\) and \(\textsc{e-sl}_{in}(j)\) starting from \(p^{\prime}\) and \(q\), respectively. While performing the linear sweep, we add the corresponding journey for each matched hub we found to a temporary set, say \(M\). Once \(M\) is computed, we order the journeys in \(M\) with respect to their arrival times. Finally, we process journeys in \(M\) sequentially, and add a journey \(J\) to profile only if the accumulated number of transfers in \(J\) is less than the number of transfers for journeys added so far to profile. Finally, we return profile as the answer to the profile query \(\textsc{mc-ea}(s_{i},s_{j},\tau)\). ### Updating the Extended Stop Labeling

If an extended stop labeling e-sl is available and the network undergoes a delay then, after updating both the wred-te graph and the 2 hc-sp labeling, the trivial way to update e-sl is to recompute it from scratch. However, to reduce the required computational effort, in what follows we propose a procedure that is able to exploit the information about the changed part of the graph and the 2 hc-sp labeling to update the corresponding extended stop labeling in very short time. In details, the procedure for dynamically updating the extended stop labeling requires, during the execution of Algorithms 7-11, to compute two sets of so-called _updated stops_, denoted, respectively, by \(\textsc{US}_{out}\) and \(\textsc{US}_{in}\). In the multi-criteria case these two sets are defined as the stops \(s_{i}\in\textsc{S}\) such that vertices in \(\textsc{DV}[i]\) (\(\textsc{AV}[i]\), respectively) had their time value or forward label (backward label, respectively) changed during Algorithm dag-decpll. Once this is done we update the extended stop labeling e-sl by recomputing only those entries of \(\textsc{e-sl}_{out}(i)\) (\(\textsc{e-sl}_{in}(i)\), respectively) for each \(s_{i}\in\textsc{US}_{out}\) (for each \(s_{i}\in\textsc{US}_{in}\), respectively). We are now ready to provide the following results. **Theorem 7** (Complexity of Multi-criteria d-ptl). : _Algorithm d-ptl in the multi-criteria setting takes \(\mathcal{O}(|\mathcal{C}|^{4})\) computational time in the worst case._

Proof. : The proof can be derived by the argument given in the proof of Theorem 2. In particular, we know that the worst case time complexity of both inpll and dag-decpll is \(\mathcal{O}(|V|^{3})\) for a graph with \(|V|\) vertices and that these routines, in Algorithm d-ptl, can be executed, in the worst case, for all stops, which are \(|\textsc{S}|\leq|\mathcal{C}|\). Since \(|V|\in\mathcal{O}(|\mathcal{C}|)\) for any wred-te graph, the claim follows. ``` Input: Directed Acyclic Graph \(G\), 2 hc-sp labeling l of \(G\), vertex \(x\) to be removed from \(G\), sets \(\textsc{left}_{x}\) and \(\textsc{right}_{x}\). 1 foreach\(v\in\textsc{right}_{x}\) in increasing order of \(t(v)\)do
2\(\textsc{C}_{out}(v)\leftarrow\mathcal{O}\) ;
3 foreach\((u,\delta_{uv})\in\textsc{L}_{in}(v)\)do
4 if\(u\
eq v\)then
5 if(\(u\in\textsc{left}_{x}\)and\((u,\delta_{uv})\) is not marked) or\(u=x\)then
6\(\textsc{L}_{in}(v)\leftarrow\textsc{L}_{in}(v)\setminus\{(u,\delta_{uv})\}\);
7 foreach\(u\in\textsc{NS}_{in}^{G}(v)\)do
8 foreach\((h,\delta_{uv})\in\textsc{L}_{in}(u)\)do
9 if\(h\in\textsc{left}_{x}\)and\(h\
ot\in\textsc{C}_{in}(v)\)then
10\(\textsc{C}_{in}(v)\gets\textsc{C}_{in}(v)\cup\{h\}\) ;
11 foreach\(w\in\textsc{C}_{in}(v)\) in increasing order of \(t(w)\)do
12\(d\leftarrow\min\limits_{u\in\textsc{NS}_{in}^{G}(v)}\{\textsc{Query}(w,u, \textsc{L})+\textsc{Query}(u,v,\textsc{L})\}\) ;
13 if\(\textsc{query}(w,v,\textsc{L})>d\)then
14 if\(l(v)<l(w)\)then
15\(\textsc{L}_{in}(v)\leftarrow\textsc{L}_{in}(v)\cup\{(w,d)\}\);
16 else
17\(\textsc{L}_{out}(w)\leftarrow\textsc{L}_{out}(w)\cup\{(v,d)\}\);
18