# Journey Planning Algorithms for Massive Delay-Prone Transit Networks +
## 3 Basic Public Transit Labeling
### Reduced Time-Expanded Graph  
The input timetable \(\mathcal{T}=(\mathcal{Z},\mathsf{S},\mathcal{C})\) associated to the transit network is modelled via a reduced time-expanded graph (red-te) [2]. In the case of an aperiodic timetable, the red-te graph is a directed acyclic graph (DAG) \(G=(V,A)\)[13]. Starting from initially empty sets of vertices \(V\) and arcs \(A\), the DAG \(G\) associated with the aperiodic timetable \(\mathcal{T}\) is built as follows. For each elementary connection \(c=(Z,s_{i},s_{j},t_{d},t_{a})\):  
* two vertices are added to \(V\), namely a departure vertex \(v^{c}_{d}\) and an _arrival vertex_\(v^{c}_{a}\), respectively, each having an associated time \(time(v^{c}_{d})\) and \(time(v^{c}_{a})\), respectively, such that \(time(v^{c}_{d})=t_{d}\) and \(time(v^{c}_{a})=t_{a}\). Departure and arrival vertices are logically stored within the corresponding stop, that is each vertex \(v^{c}_{d}\) (\(v^{c}_{a}\), respectively) belongs to the set of departure (arrival, respectively) _vertices_\(\textsc{dv}[i]\) (\(\textsc{av}[j]\), respectively) of stop \(s_{i}\) (\(s_{j}\), respectively);
* a directed connection arc \((v^{c}_{d},v^{c}_{a})\) is added to \(A\), connecting the corresponding departure and arrival vertices.  
Furthermore:  
* for each trip trip \(\textsc{trip}=(c_{0},c_{1},\ldots,c_{k})\), and for each connection \(c_{i}\in\textsc{trip}\), \(0\leq i<k\), a bypass arc \((v^{c_{i}}_{a},v^{c_{i+1}}_{a})\) is added to \(A\), connecting the two arrival vertices of \(c_{i}\) and \(c_{i+1}\).
* for each pair of vertices \(u,v\in\textsc{dv}[i]\), a waiting arc \((u,v)\) is added to \(A\) if \(time(v)\geq time(u)\), and there is no \(w\) in \(\textsc{dv}[i]\) such that \(time(v)\geq time(w)\geq time(u)\).
* for each \(u\in\textsc{av}[i]\) and for each \(v\in\textsc{dv}[i]\), a transfer arc \((u,v)\) is added to \(A\) if \(time(v)\geq time(u)+\textsc{mt}_{i}\), and there is no \(w\in\textsc{dv}[i]\) such that \(time(w)<time(v)\) and \(time(w)\geq time(u)+\textsc{mt}_{i}\).  
An example of construction of red-te graph is given in Figure 1, built using the timetable of Table 1 as input.  
In the remainder of the paper, given a directed graph \(G=(V,A)\): we denote by \(N_{out}(v)=\{u\in V\::(v,u)\in A\}\) (\(N_{in}(v)=\{u\in V\::(u,v)\in A\}\), respectively) the set of _outgoing_ (_incoming_,  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Departure Stop** & **Arrival Stop** & **Departure Time** & **Arrival Time** & **VehicleID** & **Minimum Transfer Time** \\ \hline \(-\) & \(X\) & \(-\) & 00:05 & \(\alpha\) & 5 \\ \(-\) & \(X\) & \(-\) & 00:07 & \(\beta\) & 5 \\ \(X\) & \(Y\) & 00:10 & 00:15 & \(\alpha\) & 5 \\ \(X\) & \(Y\) & 00:15 & 00:20 & \(\beta\) & 5 \\ \(Y\) & \(-\) & 00:20 & \(-\) &  
respectively) neighbors of a vertex \(v\in V\). We say a vertex \(u\)_is reachable from_ (_reaches_, respectively) another vertex \(v\) if and only if there exists a path from \(v\) to \(u\) (from \(u\) to \(v\), respectively) in \(G\), that is, a sequence of arcs \(((v,v_{1}),(v_{1},v_{2}),\ldots,(v_{k},u))\).  
Moreover, we say a path \(P\) connecting two vertices \(u\) and \(v\) is a shortest path between \(u\) and \(v\) in \(G\) if \(P\) is a path from \(u\) and \(v\) in \(G\) whose length is minimum among all paths connecting \(u\) and \(v\) in \(G\). Such length is given by the sum of the weights of the arcs in the path, it is typically denoted by \(d_{G}(u,v)\) and it is often referred to as the distance from \(u\) to \(v\) in \(G\).