Core pattern

Graphs: fastest route across the city

Learn the graphs pattern through one picture you won’t forget, worked on Dijkstra.

The example problem

Junctions 1 to n are connected by one-way roads with travel times (times[i] = (u, v, w)). A signal starts at junction k. Return how long until every junction has received it (the largest of the fastest times), or −1 if some junction can never be reached.

Input:  times = [[1,2,4], [1,3,1], [3,2,2], [2,4,1], [3,4,5], [4,5,3]], n = 5, k = 1
Output: 7   (junction 5 is last: 1 → 3 → 2 → 4 → 5)

Picture it

Picture a city map: pins are junctions, roads are labelled with minutes. Each pin shows its best known time (∞ at first). We always “lock in” the unfinished pin with the smallest time, because no route through farther pins could beat it. From that pin we check each road: if going through it is faster, update the neighbour’s time.

The key idea

Dijkstra: a min-heap of (time, junction); pop the closest, relax its roads. Works when no road has negative time.

Python

def network_delay_time(times, n, k):
    roads = defaultdict(list)
    for u, v, w in times:         # one-way
        roads[u].append((v, w))
    dist = {k: 0}
    pq = [(0, k)]
    while pq:
        d, u = heappop(pq)         # closest
        if d > dist[u]:
            continue
        for v, w in roads[u]:
            if d + w < dist.get(v, inf):
                dist[v] = d + w
                heappush(pq, (dist[v], v))
    if len(dist) < n:
        return -1  # someone never hears
    return max(dist.values())

Practise graphs

NeetCode 150 problems that use it

Graphs · Advanced Graphs ·