LeetCode 743 · Advanced Graphs

Dijkstra, explained with a picture

Fastest route across the city.

MediumAdvanced Graphs
▶ Watch it step by step

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

How to recognise it

  • A weighted directed graph (one-way roads with travel times) and a single starting point.
  • The question needs the shortest time from the start to every node, then a summary of those times (here, the largest).
  • All weights are non-negative, so a path never gets cheaper by going further.
  • With up to 100 nodes and 6,000 roads you want near-linear work in the number of roads.

Start with brute force

The first idea, trying every path from the start, is exponential. A simple fix is to keep a best-known time for every junction and keep relaxing every road (setting dist[v] = dist[u] + w whenever that is smaller) until a full pass changes nothing.

def network_delay_brute(times, n, k):
    dist = [inf] * (n + 1)
    dist[k] = 0
    changed = True
    while changed:
        changed = False
        for u, v, w in times:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
    m = max(dist[1:])
    return -1 if m == inf else m

Each pass costs O(E), and up to n passes may be needed, so time is O(V·E): about 6 × 10^5 steps for 100 nodes and 6,000 roads, which is fast enough here, but about 10^10 for 10^5 nodes and roads. Space is O(V). This works because of the non-negative weights.

From brute force to the idea

  1. Find the waste. The brute force relaxes every road on every pass, including roads whose start junction has not improved since last time.
  2. Settle the closest first. If all times are non-negative, the unsettled junction with the smallest tentative time cannot be improved later, because any other route to it would pass through something at least as far away.
  3. Use a min-heap. pq holds (time, junction). Popping gives the closest junction u with its time d.
  4. Relax only its roads. For each road (v, w) from u, if d + w beats the best known time for v, record it and push (d + w, v).
  5. Skip stale entries. A junction can be pushed more than once. If the popped d is larger than dist[u], a better entry was already processed, so continue.
  6. Answer. If fewer than n junctions were reached, someone never hears, so return -1. Otherwise the signal reaches everyone when the slowest junction hears it: max(dist.values()).

The key idea: always finalise the nearest unsettled junction, then relax only its outgoing roads.

The key idea

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

Python solution

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())

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import defaultdict from heapq import heappush, heappop from math import inf

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Repeated relaxation (brute force)O(V·E): up to V passes over all roadsO(V): the distance list
Dijkstra with a heap (shown code)O(E log V): each road causes at most one push, and each push or pop costs O(log V)O(V + E): the road lists, the distance dictionary and the heap

Edge cases

  • One junction (n = 1, no roads, k = 1): returns 0.
  • A junction the signal cannot reach (n = 2, [[1,2,1]], k = 2): returns -1, because the roads are one-way.
  • Two routes ([[1,2,1],[2,3,2],[1,3,4]], k = 1): returns 3, the faster route through junction 2.
  • Zero-time roads are fine: [[1,2,0],[2,1,0]] returns 0.
  • Negative times: not supported, because a settled junction could later be improved. Use Bellman-Ford for those.
  • Imports: heappush and heappop from heapq, inf from math, and defaultdict. Junctions are numbered from 1.

Common mistakes

  • Using BFS, which counts roads, not time.
  • Returning the sum of the times instead of the largest.
  • Forgetting the -1 check, so unreachable junctions are ignored.
  • Missing the stale-entry check, which still gives the right answer but processes entries needlessly.
  • Treating the roads as two-way when they are one-way.
Your turn: how many hear it in time?

Return how many junctions receive the signal within time T (the start counts). Describe what changes, then write it if you like.

Compare with our answer

Run the same Dijkstra, but stop as soon as the closest remaining entry is later than T. Pops come out in non-decreasing time, so everything after that is also too late.

def reached_within(times, n, k, T):
    roads = defaultdict(list)
    for u, v, w in times:
        roads[u].append((v, w))
    dist = {k: 0}
    pq = [(0, k)]
    while pq:
        d, u = heappop(pq)
        if d > T:
            break
        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))
    return sum(1 for d in dist.values() if d <= T)

Time O(E log V), space O(V + E).

A strong answer mentions: stopping early once the popped time exceeds T, why pop order makes that safe, and counting the junctions whose final time is at most T.

Check what stuck

1. A map has roads with lengths in kilometres, all greater than zero. You must find the shortest distance from your home to every other town. Which approach fits best?

2. Why does the shown code have if d > dist[u]: continue after popping?

3. A learner deletes the lines if len(dist) < n: return -1. Which input now returns a wrong answer?

Score 60% or more and the lesson is marked complete.