# Journey Planning Algorithms for Massive Delay-Prone Transit Networks +
## 5 Dynamic Public Transit Labeling
Concerning Algorithm 2, notice that all sub-routines require a time that is linear in the size of the processed stop (i.e., in the number of associated arcs). Hence, by summing up the contribution for all considered stops (those traversed by the trip from connection \(c_{m}\) to \(c_{k}\)), we obtain that updating the graph via Algorithm ins-d-ptl takes \(\mathcal{O}(|\mathcal{C}|)\), as \(|\mathcal{C}|\geq\max\{|\textsc{S}|,|\mathcal{Z}|\}\) and, in the worst case, the affected trip can traverse all stops of the network. On top of that, we need again to consider the time for executing dec-bu and inc-bu, which are performed again \(|\textsc{S}|\leq|\mathcal{C}|\) times in the worst case. Since \(|V|\in\mathcal{O}(|\mathcal{C}|)\), we have that Algorithm ins-d-ptl runs in \(\mathcal{O}(|\mathcal{C}|^{3}\log|\mathcal{C}|)\) worst case time. Concerning Algorithm 3, it scans label entries of vertices in both us\({}_{in}\) and US\({}_{out}\) in non-increasing and non-decreasing order, respectively (thus requiring either to sort them or to use a priority queue). In both cases, we have an additional logarithmic factor in terms of computational time per vertex. Since all vertices for all stops can be \(\mathcal{O}(|\mathcal{C}|)\), and since sorting stop labels with respect to hub vertices at the end of the procedure requires \(\mathcal{O}(|\mathcal{C}|\log|\mathcal{C}|)\) worst-case time, it follows that the worst case time of Algorithm 3 is \(\mathcal{O}(|\mathcal{C}|\log|\mathcal{C}|)\). If we sum up the complexities of Algorithms 1, 2 and 3, the claim follows. Notice that, Theorem 2 implies that d-ptl, in the worst case, is slower than the reprocessing from scratch via ptl, whose worst case running time is cubic in the size of the graph due to the recomputation of the labeling [20]. However, our experimental study, which is described in Section 7, clearly shows that d-ptl always outperforms ptl in practice. ## 6 Dynamic Multi-Criteria Public Transit Labeling

In this section, we extend d-ptl to handle the multi-criteria setting. We refer to the extended version as multi-criteria d-ptl. We remark that, to update the data structures employed by the basic PTL framework, D-PTL exploits the structure of the red-TE graph and alternates phases of modifications of the graph itself with corresponding updates of the reachability labeling via the procedures given in [24]. These phases are bundled in two blocks, namely the _removal phase_ (Algorithm rem-d-ptL, see Algorithm 1) and _insertion phase_ (Algorithm ins-d-ptL, see Algorithm 2) that update the labeling along with the graph. The above two routines, however, cannot be directly employed within the multi-criteria PTL approach, that relies on a shortest path labeling rather than on a reachability one. In particular, while the modifications to the graph applied by the two routines are almost same for wred-TE graphs (the only exception is that whenever we add a transfer arc we need also to add a suited intermediate vertex for modeling a transfer, whenever the two vertices are associated to connections of different trips. ), we cannot use algorithm butterfly, which is designed for reachability labelings, to update the shortest path labeling at hand. Hence, we need to replace dec-bu (in lines 14 and 21 of Algorithm 1) and inc-bu (in lines 11, 17, 20, 26, and 30 of Algorithm 2) with decremental and incremental algorithms that are suited to update the 2 hc-SP labeling. To this regard, we can employ the decremental algorithm decpll of Reference [21] and the incremental algorithm incpll of Reference [15], respectively, that are designed to update 2 hc-SP in general graphs.