# Journey Planning Algorithms for Massive Delay-Prone Transit Networks +
## 3 Basic Public Transit Labeling
### Shortest Path Labeling  
Given a directed graph \(G\), a _2-Hop-Cover shortest path labeling_ (shortly, 2 hc-sp labeling) \(\mathsf{L}\) of \(G\) associates two labels \(\mathsf{L}_{in}(v)\) and \(\mathsf{L}_{out}(v)\) to each vertex \(v\) in \(V\), called backward label and forward label, respectively. Differently from reachability labelings, in this case, each label contains additional information, namely each entry in \(\mathsf{L}_{in}(v)\) (\(\mathsf{L}_{out}(v)\), respectively) is of the form \((h,\delta_{hv})\) (\((h,\delta_{vh})\), respectively), where:  
* \((h,\delta_{hv})\) represents a vertex \(h\) in \(G\) from which \(v\) can be reached via a shortest path of length \(\delta_{hv}\);
* \((h,\delta_{vh})\) represents a vertex \(h\) in \(G\) reachable from \(v\) via a shortest path of length \(\delta_{vh}\);
* label entries satisfy the so-called _cover property_ that is, for any pair of vertices \(u,v\in V\), the distance \(d(u,v)\) (i.e., the weight of the shortest path) from \(u\) to \(v\) in \(G\) can be retrieved by a linear scan of the two labels of \(u\) and \(v\) only. In details, a query on the distance is defined as follows:  
\[\textsc{Query}(u,v,\mathsf{L})= \begin{cases}\min_{h\in V}\{\delta_{uh}+\delta _{hv}\,|\,(h,\delta_{uh})\in\mathsf{L}_{out}(u)\wedge(h,\delta_{hv})\in \mathsf{L}_{in}(v)\}&\text{if }\mathsf{L}_{out}(u)\cap\mathsf{L}_{in}(v)\
eq \emptyset\\ \infty&\text{otherwise.}\end{cases} \]  
It can be shown that, for any 2 hc-sp labeling, \(\textsc{Query}(u,v,\mathsf{L})\) always equals \(d(u,v)\)[26], that is for any two connected vertices \(u,v\in V\), we have \(\mathsf{L}_{out}(u)\cap\mathsf{L}_{in}(v)\
eq\emptyset\) and the minimum value of the sums equals the weight of a shortest path in the graph. In particular, in this case we call hub vertices for pair \(u,v\) the vertices in  
\[\{k:k\in\arg\min_{h\in V}\{\delta_{uh}+\delta_{hv}\,|\,(h,\delta_{uh})\in \mathsf{L}_{out}(u)\wedge(h,\delta_{hv})\in\mathsf{L}_{in}(v)\}\},\]  
where each element in said set is a vertex lying on a shortest path from \(u\) to \(v\) in \(G\). In the above definition we slightly overload our notation by saying that \(h\) belongs to \(\mathsf{L}_{out}(v)\) (\(\mathsf{L}_{in}(v)\), respectively) whenever \((h,\delta_{vh})\in\mathsf{L}_{out}(v)\) (\((h,\delta_{hv})\in\mathsf{L}_{in}(v)\), respectively). Note that, despite the same nomenclature, the notion of hub vertex here is more restrictive with respect to reachability labelings, as it requires the vertex to be on a shortest path rather than on any path. To this regard, for 2 hc-sp labelings, the following definition can be given. We refer the reader to Reference [29] for more details. **Definition 4** (Induced Path). : _Given a graph \(G=(V,A)\), a pair \(s,t\in V\) and a 2 hc-sp labeling \(L\) of \(G\), a shortest path \(P\) is induced by \(L\) for pair \(s,t\in V\) if, for any two vertices \(u\) and \(v\) in \(P\), there exists a hub \(h\) of pair \((u,v)\) such that \(h\in P\), or \(h=u\), or \(h=v\). The set of shortest paths between vertices \(s\) and \(t\) induced by \(L\) is denoted by \(\textsc{Path}(s,t,L)\)._  
Finally, note that, as well as reachability labelings, also for shortest path labelings the size of the labeling is given by the sum of the sizes of the label entries and it is known that computing a 2 hc-sp covering of the graph of minimum size is NP-Hard, by a simple reduction to the 2 hc-r case [26]. However, numerous approaches have been presented to heuristically improve both the time to compute the labeling and its size [24; 27; 28]. A reference approach for DAGs (as the wred-te is) is that of Reference [24] which, in the case of shortest path labelings, relies on computing a topological order over the vertices of \(G\). A topological order \(T\)on the vertex set \(V\) for a DAG is a total ordering defining a precedence relationship among the vertices such that for any arc \((u,v)\) in \(G\) we have \(t(u)<t(v)\), where \(t(w)\) is the position in the ordering of the generic vertex \(w\in V\).