# Journey Planning Algorithms for Massive Delay-Prone Transit Networks +
## 5 Dynamic Public Transit Labeling
Furthermore, we obtain the final version L of the 2 hc-r labeling (see Line 30). An example of execution of the insertion phase is shown in Figure 3. In addition, for the sake of simplicity in understanding, we show an example of execution of the procedures for: (i) rewriting transfer arcs (Algorithm 5) and waiting arcs (Algorithm 4) to a departure vertex in Figure 4; and (ii) rewiring arcs to an arrival vertex (Algorithm 6) in Figure 5.

Figure 4: An example of execution of the procedure for rewiring transfer and waiting arcs given in Algorithms 4 and 5, respectively. On the left we show part of a sample graph, relative to a stop \(P\) with the assumption that \(\textsc{mtt}_{P}=5\) min, that is violating the red-te properties. In particular, no waiting and transfer arcs are associated with the vertex colored in green. To restore the red-te properties both transfer and waiting arcs must be added. Concerning the former, Algorithm 5 is executed and the resulting graph is shown in the middle, where dashed arcs in red (arcs in blue, respectively) are the removed arcs (newly inserted arcs, respectively). Regarding the latter, instead, Algorithm 4 is executed. The resulting red-te graph (on the right side) is the final outcome. Dashed arcs in red are the removed arcs, while arcs in blue are the newly added ones. Figure 3: The red-te graph obtained after performing Algorithm ins-d-ptl (Algorithm 2) on the graph of Figure 2. Newly added vertices (arcs, respectively) are drawn in green (blue, respectively). The dashed arc drawn in red is the waiting arc of Figure 2 that is removed in the insertion phase. Notice that, the above theorem is based on the correctness of the approaches in References [2; 13; 24]. In particular, it is easy to see that whenever we update the graph, we do it by preserving the constraints imposed by the red-te model on both vertices, by suitably modifying connection arcs and associated waiting, bypass, and transfer arcs. In more details, it is easy to prove, by contradiction, that after the execution of Algorithms 1 and 2, \(G\) is a red-te graph. Concerning the labeling data structures, observe that after each change to \(G\) we use either dec-bu or inc-bu, depending on the type of performed modification. These algorithms have been shown to compute a labeling that is a 2 hc-r labeling for the modified graph [24]. Hence, at the end of Algorithm 2, L is a 2 hc-r labeling for \(G\). Finally, Algorithm 3 applies the definition of stop labeling, by updating the entry of a stop with the proper hub vertices and times values. Hence, after the execution of Algorithm 3, sl is a stop labeling of L and the theorem follows. **Theorem 2** (Complexity of Basic d-ptl). : _Algorithm d-ptl takes \(\mathcal{O}(|\mathcal{C}|^{3}\log|\mathcal{C}|)\) computational time in the worst case._

Proof. : The complexity of Algorithm d-ptl is given by the sum of the complexities of Algorithms 1, 2 and 3. In what follows, we analyze separately the three algorithms. Concerning Algorithm 1, we first bound the cost of executing Lines 1-21, that is, the amount of computational time per connection. Lines 1-8 require a time that is linear in the number of neighbors (incoming and outgoing) of \(v_{d}^{c_{j}}\), which is a constant in red-te graphs, while lines 9-21 spend a time that grows as said number of neighbors times the time required for performing the dynamic algorithms dec-bu and inc-bu. Each execution of these algorithms takes \(\mathcal{O}(|V|^{2}\log|V|)\) in the worst case [24]. Thus, lines 1-21 require \(\mathcal{O}(|V|^{2}\log|V|)\) time in the worst case. These lines are repeated for all stops traversed by the vehicle of the trip from connection \(c_{m}\) to \(c_{k}\), therefore in the worst case for all stops of the transit network, which are \(|\textsc{S}|\leq|\mathcal{C}|\). Since \(|V|\in\mathcal{O}(|\mathcal{C}|)\), we have that Algorithm rem-d-ptl runs in \(\mathcal{O}(|\mathcal{C}|^{3}\log|\mathcal{C}|)\) worst case time.