Problem Definition (Optimal Temporal Paths)

A temporal edge is $(u,v,t,\lambda)$ meaning edge $(u,v)$ is usable at time $t$ and traversal takes $\lambda\ge 0$ (in point models set $\lambda\in{0,1}$).

A temporal path / journey $P=e_1,\dots,e_k$ with $e_i=(v_{i-1},v_i,t_i,\lambda_i)$ is time-respecting if

• non-strict: $t_{i+1}\ge t_i+\lambda_i$ for all $i<k$,
• strict: $t_{i+1}> t_i+\lambda_i$ for all $i<k$.

We write:

• $\mathrm{dep}(P)=t_1$ (departure time),
• $\mathrm{arr}(P)=t_k+\lambda_k$ (arrival time),
• $|P|=k$ (hop count),
• $\mathrm{dur}(P)=\mathrm{arr}(P)-\mathrm{dep}(P)$ (duration).

By default, waiting at intermediate vertices is allowed. A release time $t_0$ restricts attention to journeys with $\mathrm{dep}(P)\ge t_0$.

📁 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.

Design Notes & Relationships

• Different optima: The three criteria can pick different journeys.
  • Earliest-arrival minimises when you arrive, possibly by departing early and waiting.
  • Fastest minimises in-transit time; it may depart later than the earliest-arrival path.
  • Shortest minimises hops; it need not be earliest nor fastest.
• Strict vs non-strict: Choose one globally to match your setting; it affects feasibility and optimality.
• Waiting constraints: You can add a restlessness bound $\Delta$ (waiting $\le \Delta$ at each intermediate node).
• Lexicographic variants (common in practice):
  • “Earliest-arrival, then shortest” (break ties on hops).
  • “Fastest, then earliest-arrival” (break ties on arrival time).