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 (this is what licenses Dijkstra)

Think about it first

TL;DR

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

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.

class Solution:
    def networkDelayTime(self, 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 the constraints kill it.

Approach 2 — Bellman-Ford

The insight: a shortest path in a graph with n nodes uses at most n - 1 edges, and one pass of “relax every edge” extends correct answers by one more edge. So n - 1 passes over the flat edge list — no adjacency structure, no heap — provably converge. Bellman-Ford is the workhorse for shortest paths when you want dead-simple code or must tolerate negative weights.

class Solution:
    def networkDelayTime(self, 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

The insight: with positive weights, the unsettled node with the smallest tentative time can never be improved later — 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, relax its outgoing edges. Lazy deletion (skip a popped node that’s already settled) avoids a decrease-key operation.

import heapq

class Solution:
    def networkDelayTime(self, 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 → O(E log E) = O(E log V) time, O(V + E) space. The right default 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.