Time-respecting paths
Sequence of edges (v₀, v₁, t₁), (v₁, v₂, t₂), … with t₁ ≤ t₂ ≤ … Reachability now time-dependent.
Advertisement
Fastest/earliest arrival
Multiple 'shortest path' notions: minimize arrival time, minimize duration, minimize hops. Different algorithms.
Advertisement
Complexity
Sort edges by time. Modified BFS/Dijkstra. O(V + E log E) typical.
Time-varying networks
Twitter mentions. Contact networks (epidemiology). Financial transactions.