Network Delay Time

Problem

A network has n nodes labeled 1 to n. You’re given directed links times[i] = [u, v, w], meaning a signal sent from node u reaches node v after w units of time.

A signal is broadcast from node k. It propagates along every outgoing link simultaneously, and each node relays it onward the moment it arrives. Return the time at which the last node receives the signal — or -1 if some node never receives it.

Equivalently: compute the shortest travel time from k to every node, then return the maximum of those times (or -1 if any node is unreachable).

Examples

• times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 → 2 — nodes 1 and 3 hear it at t=1, node 4 at t=2.
• times = [[1,2,1]], n = 2, k = 1 → 1 — the single link delivers at t=1.
• times = [[1,2,1]], n = 2, k = 2 → -1 — node 1 has no incoming path from node 2.

Constraints

• 1 <= n <= 100, 1 <= k <= n
• 1 <= len(times) <= 6000
• 1 <= w <= 100; all weights are positive, which is what makes Dijkstra applicable

Think about it first

TL;DR

Single-source shortest paths with Dijkstra and a min-heap; the answer is the maximum distance. O(E log V) time, O(V + E) space.

The examples below all run on this graph (times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2):

graph LR
    2 -->|1| 1
    2 -->|1| 3
    3 -->|1| 4

Approach 1 — Brute force (DFS, re-explore on improvement)

Push the signal along every path recursively, recording the best arrival time seen at each node and re-exploring whenever we arrive earlier than before. Positive weights make the “only continue if strictly earlier” check terminate.

def networkDelayTime(times: list[list[int]], n: int, k: int) -> int:
    adj = {i: [] for i in range(1, n + 1)}
    for u, v, w in times:
        adj[u].append((v, w))

    arrival = {i: float("inf") for i in range(1, n + 1)}

    def dfs(node: int, elapsed: int) -> None:
        if elapsed >= arrival[node]:
            return
        arrival[node] = elapsed
        for nxt, w in adj[node]:
            dfs(nxt, elapsed + w)

    dfs(k, 0)
    ans = max(arrival.values())
    return -1 if ans == float("inf") else ans

Complexity: exponential in the worst case. A node can be re-processed once per distinct improving path, and path counts grow combinatorially. With 6000 edges this does not pass.

Approach 2 — Bellman-Ford

A shortest path in a graph with n nodes uses at most n - 1 edges, and one pass of “relax every edge” extends every correct answer by one more edge. So n - 1 passes over the flat edge list converge, with no adjacency structure and no heap. Bellman-Ford is the simplest option to write and the one to use when weights can be negative.

def networkDelayTime(times: list[list[int]], n: int, k: int) -> int:
    INF = float("inf")
    dist = [INF] * (n + 1)
    dist[k] = 0
    for _ in range(n - 1):
        changed = False
        for u, v, w in times:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break
    ans = max(dist[1:])
    return -1 if ans == INF else ans

Walkthrough (times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2): start dist = [_, INF, 0, INF, INF] (index 0 unused). Pass 1: edge 2→1 sets dist[1] = 1, edge 2→3 sets dist[3] = 1, edge 3→4 sets dist[4] = 2. Pass 2: nothing improves, early exit. Answer max(1, 0, 1, 2) = 2.

Complexity: O(n · E) time (here ≤ 100 · 6000 = 600k relaxations — fine), O(n) space.

Approach 3 — Dijkstra with a min-heap

With positive weights, the unsettled node with the smallest tentative time can never be improved later, because every detour through another unsettled node only adds time. Dijkstra’s algorithm turns that into a greedy loop: pop the earliest (time, node) from a min-heap, settle it permanently, and relax its outgoing edges. Lazy deletion (skip a popped node that is already settled) avoids a decrease-key operation.

import heapq

def networkDelayTime(times: list[list[int]], n: int, k: int) -> int:
    adj = [[] for _ in range(n + 1)]
    for u, v, w in times:
        adj[u].append((v, w))

    dist = {}
    heap = [(0, k)]
    while heap:
        d, node = heapq.heappop(heap)
        if node in dist:
            continue  # stale entry; node already settled earlier
        dist[node] = d
        for nxt, w in adj[node]:
            if nxt not in dist:
                heapq.heappush(heap, (d + w, nxt))
    if len(dist) < n:
        return -1
    return max(dist.values())

Walkthrough (same example): pop (0, 2) → settle node 2, push (1, 1) and (1, 3). Pop (1, 1) → settle node 1 (no outgoing edges). Pop (1, 3) → settle node 3, push (2, 4). Pop (2, 4) → settle node 4. All 4 nodes settled; answer max(0, 1, 1, 2) = 2.

Complexity: every edge pushes at most one heap entry, so O(E log E) = O(E log V) time and O(V + E) space. This is the default choice for positive-weight shortest paths.

Common pitfalls

• Returning the distance to one target instead of the max over all nodes — the broadcast ends when the last node hears it.
• Forgetting the unreachable check (len(dist) < n, or a leftover infinity) and returning infinity instead of -1.
• Off-by-one on 1-indexed nodes — size arrays n + 1 and ignore index 0, or max(dist[1:]) silently includes a bogus slot.
• Skipping the “already settled” check in lazy-deletion Dijkstra: stale heap entries then overwrite good distances or waste time re-relaxing.

Pattern takeaway

Weighted single-source shortest paths: BFS is only valid when all weights are equal; Dijkstra (greedy + min-heap) is the default when weights are positive; Bellman-Ford when weights can be negative or when a bounded number of edges/rounds is itself the constraint. When the question asks about “everyone receives / all nodes covered”, the answer is an aggregate (max) over the whole distance table, not one target’s distance.