# Journey Planning Algorithms for Massive Delay-Prone Transit Networks +
## 5 Dynamic Public Transit Labeling
Unfortunately, by preliminary experiments we conducted on some relevant instances of the problem (we recall the reader that graphs treated in this paper are specifically DAGs), we observed that, while incpll is quite fast and updates the labeling within few seconds even in very large graphs, decpll is painfully slow, and sometimes its computational time is comparable with that required for recomputing the labeling from scratch. This is most likely due to the sparse nature of the red-TE graph and to how decpll updates 2 hc-SP labelings. In more details, decpll works in three phases whose running time depends proportionally on the cardinality of the set of vertices that contain at least a label entry that is incorrect. It is easy to see that this cardinality tends to the number of vertices of the graph in DAGs in most of the cases (see Reference [21] for more details on this part of the computation). For such reasons, in what follows we propose an extension of algorithm dec-bu, named dag-decpll, that is explicitly designed to update shortest path labelings in DAGs, instead of reachability labelings, as a consequence of decremental updates to the graph. The main intuition behind dag-decpll is to exploit the specific relationships between shortest paths in DAGs, which are instead neglected by decpll, which is designed for general graphs. Given a graph \(G=(V,A)\), we discuss the new approach by focusing on how to handle the removal of a vertex, say \(x\in V\), which is the decremental operation of interest in our scenario. Note that, the routine can be easily extended to handle arc removals or arc weight increases, as discussed at the end of this section. In what follows, we call \(G^{\prime}=(V^{\prime},A^{\prime})\) the graph obtained by removing vertex \(x\) from \(V\). Furthermore, we denote by \(d_{S}(u,v)\) the distance (i.e., the weight of a shortest path) between two vertices \(u\) and \(v\) of a graph, say \(S\). and define two subsets of vertices of \(V\), namely \(\textsc{right}_{x}\) and \(\textsc{left}_{x}\), as follows:

* \(\textsc{right}_{x}\): the set of vertices of \(V\) that are reachable from \(x\) in \(G\), i.e., \(u\in\textsc{right}_{x}\) if and only if there exists a path from \(x\) to \(u\) in \(G\);
* \(\textsc{left}_{x}\): the set of vertices of \(V\) that can reach \(x\) in \(G\), i.e., \(u\in\textsc{left}_{x}\) if and only if there exists a path from \(u\) to \(x\) in \(G\). Since \(G\) is a DAG, it is easy to see that \(\textsc{right}_{x}\) and \(\textsc{left}_{x}\) are inherently disjoint, that is \(\textsc{right}_{x}\cap\textsc{left}_{x}=\emptyset\). Additionally, given the above definitions, we say a label entry \((h,\delta_{wh})\in\textsc{l}_{out}(v)\) of some vertex \(v\in V\) is _affected_ by the removal of a vertex \(x\in V\) only if \(x\) lies on a shortest path between \(v\) and \(h\) induced by \(\textsc{l}\). Similarly, a label entry \((h,\delta_{hw})\in\textsc{l}_{in}(v)\) is _affected_ by the removal of a vertex \(x\in V\) only if \(x\) lies on a shortest path between \(h\) and \(v\) induced by \(\textsc{l}\). In what follows, given a vertex \(x\in V\), we highlight some simple yet important properties of the two sets \(\textsc{right}_{x}\) and \(\textsc{left}_{x}\) that are easily derived by the structure of DAGs. **Property 1**. : _For any vertex \(v\in V\) such that \(v\
ot\in\textsc{right}_{x}\cup\{x\}\) no label entry in \(\textsc{l}_{\mathit{in}}(v)\) is affected by the removal of \(x\) from \(G\)._

**Corollary 1**. : _For any vertex \(v\in\textsc{right}_{x}\), a label entry \((h,\delta_{\mathit{th}})\) in \(\textsc{l}_{\mathit{in}}(v)\) may be affected only if \(h\in\textsc{left}_{x}\) or if \(v=x\)._

**Property 2**. : _For any vertex \(v\in V\) such that \(v\
ot\in\textsc{left}_{x}\cup\{x\}\) no label entry in \(\textsc{l}_{\mathit{out}}(v)\) is affected by the removal of \(x\) from \(G\)._

**Corollary 2**.