Temporal Graphs, in depth: time-respecting paths, earliest arrival, fastest and latest-departure algorithms

The model: contacts and time-respecting paths

The most direct representation is a contact sequence: a list of edges (u, v, t, lam) meaning that something can leave u at time t and arrive at v at time t + lam. The traversal time lam may be zero (an instant message) or positive (a flight). Undirected contacts are stored as two directed ones. Two other representations are common: a snapshot sequence, one static graph per time step, natural for data sampled at intervals; and interval edges, where an edge is present during [start, end), natural for links that stay up for a while.

A time-respecting path (also called a journey) is a sequence of contacts in which each contact departs no earlier than the previous one arrives: t[i+1] >= t[i] + lam[i]. That is the non-strict rule, which allows waiting at a vertex and allows leaving at the instant of arrival. Some applications use a strict rule, t[i+1] > t[i] + lam[i], for instance when data has one time step per snapshot and you do not want a path to cross several hops within one snapshot. The choice changes answers, so state it explicitly in every analysis. The code here uses the non-strict rule and assumes lam > 0; the zero-duration case is handled in its own section.

What breaks when edges have times

Several properties every programmer relies on for static graphs fail once order matters.

• Reachability is not transitive. If x -> y happens at time 2 and y -> z at time 1, then x reaches y and y reaches z, but x does not reach z. Reachability is therefore not an equivalence relation, and union-find style component labelling, as in the union-find article, does not apply directly.
• Aggregation lies. Collapsing contacts into a static graph keeps every edge and drops the ordering constraint, so the static graph reports paths that cannot happen. On real contact data the overestimate of reachable pairs can be large, which matters for anything from epidemic risk to influence estimates; the epidemic models article shows why spreading processes are sensitive to who can actually reach whom.
• Prefixes of optimal paths need not be optimal. The fastest journey to v may pass through u at a time that is not the fastest way to reach u, because leaving later can make the rest of the journey shorter. That breaks the subpath optimality that Dijkstra's algorithm depends on.
• Classical theorems fail. Kempe, Kleinberg and Kumar (2000) showed that Menger's theorem does not hold for vertex-disjoint time-respecting paths, and Bhadra and Ferreira (2003) showed that finding a maximum strongly connected component of a temporal graph is NP-complete, whereas the static version is linear time.

Four kinds of best path

"Shortest path" splits into four distinct questions, each with its own answer:

These are genuinely different. In the example graph below, the earliest arrival at E from A leaves at time 1 and arrives at 6 (duration 5), while the fastest journey leaves at 5 and arrives at 9 (duration 4). Neither is wrong; they answer different questions.

Earliest arrival and latest departure in one pass

Earliest arrival has a beautifully simple exact algorithm. Sort contacts by departure time and scan them once. Keep arr[v], the earliest known arrival at each vertex. A contact (u, v, t, lam) is usable if t >= arr[u] (we are at u by the time it leaves), and it improves v if t + lam < arr[v].

import math
from collections import defaultdict

def earliest_arrival(edges, src, t0):
    """edges: (u, v, t, lam) with lam > 0. Non-strict waiting. One pass, O(E log E)."""
    arr = defaultdict(lambda: math.inf)
    arr[src] = t0
    pred = {}
    for u, v, t, lam in sorted(edges, key=lambda e: e[2]):
        if t >= arr[u] and t + lam < arr[v]:
            arr[v] = t + lam
            pred[v] = (u, t)                     # reconstruct the journey backwards
    return dict(arr), pred

Why one pass suffices: when the scan reaches a contact departing at t, every contact that could bring us to u by time t departed strictly earlier (because its duration is positive) and has already been processed, so arr[u] is final for all times up to t. This is the same argument the Connection Scan Algorithm uses for public transport timetables, published by Dibbelt, Pajor, Strasser and Wagner in 2013, which routinely beats graph-based approaches on that problem because a sorted array scan is very cache-friendly. Compare it with the priority queue in Dijkstra's algorithm: the sort replaces the heap, because time itself provides the processing order.

Latest departure is the mirror image: scan contacts in decreasing departure time, starting from dep[dst] = t1, and set dep[u] = max(dep[u], t) whenever t + lam <= dep[v].

Zero-duration contacts

If some contacts take zero time, the one-pass argument breaks: contacts a -> b and b -> c, both at time 5 with zero duration, form a valid journey, but if the sort happens to place b -> c first, it is skipped before b is reached. The fix is to process each group of contacts sharing a timestamp to a fixpoint: within the group, repeat a breadth-first relaxation over the group's zero-duration contacts until nothing changes, then move on. With the strict rule the problem disappears, because a contact at time t can never extend a journey that arrived at t.

Fastest paths with Pareto lists

Fastest paths are harder because of the broken prefix property: for each vertex we must remember not one arrival time but every non-dominated pair (start, arrival). A pair dominates another if it starts no earlier and arrives no later. Following Wu and colleagues (VLDB 2014), scan contacts in departure order; for a contact out of u, find the latest start among u's pairs whose arrival is at most t, extend it, and insert the result into v's Pareto list.

def fastest(edges, src):
    """Minimum (arrival - departure) from src to every vertex. lam > 0, non-strict."""
    best = defaultdict(lambda: math.inf)
    best[src] = 0
    pareto = defaultdict(list)                   # vertex -> [(start, arrival)]
    for u, v, t, lam in sorted(edges, key=lambda e: e[2]):
        if u == src:
            start = t                            # leave the source on this contact
        else:
            usable = [s for s, a in pareto[u] if a <= t]
            if not usable:
                continue
            start = max(usable)                  # latest start that is at u in time
        arrive = t + lam
        if any(s >= start and a <= arrive for s, a in pareto[v]):
            continue                             # dominated: drop it
        pareto[v] = [(s, a) for s, a in pareto[v] if not (start >= s and arrive <= a)]
        pareto[v].append((start, arrive))
        best[v] = min(best[v], arrive - start)
    return dict(best), dict(pareto)

Kept sorted by arrival, each list is also sorted by start, so the lookup becomes a binary search; in the worst case lists grow with the number of distinct departure times at the source, which is what makes fastest paths more expensive than earliest arrival. Both functions above were checked against exhaustive enumeration of all time-respecting paths on 400 random small temporal graphs before publication. Shortest paths by total traversal time use the same scan with pairs of (arrival, cost) instead.

Worked example

Running the code on the example graph from A gives the following, with E's latest departure computed for an arrival deadline of 9:

Notice three things. The contact C-D@6 reaches D at 7, but D's only contact to E left at 5, so C cannot reach E through D at all; it reaches E only via F, which is why C's latest departure is 4. The second contact A-B@5 is useless for earliest arrival but essential for the fastest journey. And D's Pareto list holds three pairs, (1, 4), (2, 7), (5, 9), none dominating another: each is the best answer for some range of departure times.

Time-expanded graphs

Another exact approach is to turn time into structure. A time-expanded graph has a node (v, t) for every vertex and every relevant time; contacts become edges (u, t) -> (v, t + lam), and waiting becomes edges from (v, t) to the next time node of v. The result is a static directed acyclic graph, so ordinary algorithms work on it: breadth-first search for reachability, dynamic programming in topological order for earliest arrival, Dijkstra for weighted costs.

The price is size: one node per contact endpoint, which for millions of events is a large graph to materialise. The expansion pays off when you need algorithms that have no temporal version, such as max-flow over time with capacities, and when the time resolution can be coarsened. For plain reachability and path queries, the direct contact-scan algorithms are smaller, faster and easier to update.

Real event data, failure modes and trade-offs

Real event data introduces problems that textbook definitions skip.

• Out-of-order arrival. Streams deliver events late. The one-pass algorithms need sorted input, so buffer with a watermark (process events older than now minus the allowed lateness) and either drop or reprocess late contacts. Decide which, and count them.
• Clock resolution and ties. Timestamps rounded to the second create many ties. Under the non-strict rule ties allow chaining several hops within one tick; if that is not physically possible, use the strict rule or add a minimum duration.
• Windows. Many questions are about a time window, such as who could have been infected between Monday and Friday. Restrict the scan to the window rather than filtering afterwards; the restriction changes which journeys exist.
• Storage. Keep contacts in a columnar array sorted by time. Earliest arrival from one source is then a sequential scan, and many sources can be processed together with bitsets of reached sources per vertex, which is how large reachability analyses stay fast.
• Validation. Keep the exhaustive-enumeration oracle in your test suite and run it on random small graphs whenever the optimised code changes. Temporal bugs, especially at equal timestamps, are easy to introduce and invisible on happy-path data.

The main failure mode in analysis work remains aggregation: a dashboard that counts connected pairs in the static graph of a week's transactions will flag rings that are impossible in time order and miss nothing, so its errors are all false positives. The trade-off between models is fidelity against cost: contact sequences are exact but large; snapshots are compact but blur ordering within a snapshot; aggregated graphs are cheap and wrong for any question about flow. Choose the coarsest model that still answers the question correctly, and test that claim on a sample with the exact algorithm.

What to do next

1. Type in earliest_arrival and fastest, rebuild the ten-contact example and reproduce every number in the worked table.
2. Write a brute-force journey enumerator and compare it with both functions on a few hundred random small graphs, including ties and, separately, zero-duration contacts.
3. Add the same-timestamp fixpoint for zero-duration contacts and confirm the enumerator agrees once they are allowed.
4. Take a real event log (messages, transfers or a public transit timetable), compute temporal reachability from a sample of sources and compare it with static reachability.
5. Implement latest departure and use it to answer a deadline question in your own domain.
6. Build a small time-expanded graph for the example and confirm a topological-order dynamic program returns the same earliest arrivals.