# Journey Planning Algorithms for Massive Delay-Prone Transit Networks +
## 5 Dynamic Public Transit Labeling
In fact, if the topological ordering property is true on the arcs of \(G\), then it will hold on \(G^{\prime}\), as we only remove a vertex and its adjacent edges. Regarding (b), we need to show that the cover property holds for all pairs of vertices of the new graph. To this end, first observe that we remove all label entries that induce paths that include the removed vertex \(x\). Then, notice that, in both forward and backward procedures, we test the property for all and only the vertices that are affected by the removal of \(x\) (sets \(\textsc{right}_{x}\) and \(\textsc{left}_{x}\)) and that the algorithm adds new label entries to vertices by considering them in the order imposed by the topological sorting. The addition of new label entries is done incrementally, by either relying on distances that are: (i) either computed in the new graph via the customBFS; or (ii) obtained by combining distances encoded in the labeling that have surely not changed because of the removal of \(x\); or (iii) marked, and hence already updated by previous iterations of the two procedures. **Theorem 5** (Complexity of dag-decpll). : _Algorithm dag-decpll takes \(O(|V|^{3})\) in the worst case._

Proof. : Note that, for each vertex in \(\textsc{left}_{x}\), the algorithm: (i) scans the neighbors and analyzes the label sets of such neighbors (possibly removing some entries); (ii) executes procedure customBFS; (iii) processes vertices in \(\textsc{C}_{out}(v)\) and for each one of them possibly performs a marked query. Concerning (i), asymptotically this costs overall quadratic time in the size of \(G\), since the graph is acyclic and the worst case label size is \(|V|\). Concerning (ii), again we have an asymptotical time complexity that is quadratic with respect to. \(|V|\), since customBFS must explore the whole graph in the worst case. Finally, the asymptotical time complexity for executing (iii) can be bounded by observing that vertices in \(\textsc{C}_{out}(v)\) can be at most \(|V|\) and that for each of them we may execute a constant number of queries, which take \(O(|V|)\) each. Similar considerations can be done to bound the time spent by the algorithm for each vertex in \(\textsc{right}_{x}\), with the exception of procedure customBFS which is not executed, as vertices in \(\textsc{left}_{x}\) have already been processed. Therefore the claim follows. **Theorem 6** (Correctness of Multi-criteria d-ptl). : _Given an input timetable and a corresponding wred-te graph \(G\). Let \(\textsc{L}\) be a 2 hc-sp labeling of \(G\) and let \(\textsc{e-sl}\) be an extended stop labeling associated to \(\textsc{L}\) Assume \(\delta>0\) is a delay occurring on a connection, i.e. an increase of \(\delta\) on its departure time. Let \(G^{\prime}\), \(\textsc{L}^{\prime}\), and \(\textsc{e-sl}^{\prime}\) be the output of d-ptl when applied to \(G\), \(\textsc{L}\) and \(\textsc{e-sl}\), respectively, by considering the delay, in the multi-criteria setting. Then: (i) \(G^{\prime}\) is a wred-te graph for the updated timetable; (ii) \(\textsc{L}^{\prime}\) is a 2 hc-sp labeling for \(G^{\prime}\); (iii) \(\textsc{e-sl}^{\prime}\) is an extended stop labeling for \(\textsc{L}^{\prime}\)._

Proof. : The correctness of d-ptl in the multi-criteria case is based on that of the approach in [15] and on Theorem 4. In particular observe that, whenever we update the graph, we do it by preserving the constraints imposed by the wred-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 the d-ptl algorithm for the multi-criteria case, \(G\) is a wred-te graph. Concerning the labeling data structures, observe that after each change to \(G\) we use either dag-decpll or INcpll, depending on the type of performed modification. These algorithms have been shown to compute a labeling that is a 2 hc-sp labeling for the modified graph (see Theorem 4 or the proof in [24]).