Optimal temporal paths (shortest, earliest, fastest) generalize shortest static paths to moving through space and time — providing three perspectives of optimality: minimum number of hops, earliest arrival time, minimum travel time.
<aside> <img src="/icons/new-folder_yellow.svg" alt="/icons/new-folder_yellow.svg" width="40px" />
Definition: (optimal temporal paths)
A temporal path $P=(e_1,\dots,e_\ell)$ with $e_i=(v_{i-1},v_i,t_i)$ is a collection of temporal edges with non-decreasing time labels $t_i\leq t_{i+1}$ forming a path in the footprint.
The strict temporal path must satisfy $t_i<t_{i+1}$, otherwise it is a non-strict temporal path.
A vertex $u$ can reach a vertex $v$ if there exists a temporal path from $u$ to $v$. If all reachability of $\mathcal{G}$ is considered with only (non-)strict temporal paths, then $\mathcal{G}$ is called a (non-)strict temporal graph.
We denote:
By default, waiting at intermediate vertices is allowed.
📁 Definition: Earliest-Arrival (Foremost) Path
Given $s,t\in V$ and $t_0$, an earliest-arrival (aka foremost) path minimises $\mathrm{arr}(P)$ among all journeys $P:s\rightsquigarrow t$ with $\mathrm{dep}(P)\ge t_0$.
📁 Definition: Shortest (Fewest-Hops) Temporal Path
Given $s,t,t_0$, a shortest temporal path minimises the hop count $|P|$ among all feasible journeys. (Common tie-breakers: smaller $\mathrm{arr}(P)$ or smaller $\mathrm{dur}(P)$.)
📁 Definition: Fastest (Minimum-Duration) Temporal Path
Given $s,t,t_0$, a fastest temporal path minimises $\mathrm{dur}(P)$ among all feasible journeys.