A telemetry bus injects a heartbeat at service k. Each times[i] = [u, v, w] is a directed latency from u to v. The dashboard wants one number: when has every service heard. The intern BFS’d hop count. Unit latencies in staging matched. Mixed p95s in production returned the two-hop path of 400+350 while a three-hop of 8 ms each sat unused. They switched to relaxing every edge n - 1 times. A dozen services returned. A few thousand on a dense mesh were still relaxing when the request timed out.

Network Delay Time asks for the time until every node has heard a signal from k — the maximum single-source shortest-path distance, or -1 if a node is unreachable. A graph of directed weighted edges already gives neighbors for free. Relaxing everything uses that and still pays O(n m).

This is an interview writeup, not a layout lecture. That post owns adjacency list versus matrix. Dijkstra owns settle-the-closest and lazy re-push. The heap post owns sift. Here we only care about a min-heap of (dist, node), skipping stale pops, and taking the max of dist[1..n].

The problem

n nodes labeled 1 through n. times[i] = [u, v, w] is a directed edge u → v of non-negative weight w. A signal starts at k at time 0. Return the time when every node has received it — equivalently, max dist[v] from k — or -1 if some node never hears.

n = 4, k = 2, times = [[2,1,1],[2,3,1],[3,4,1]]                              →  2
n = 2, k = 1, times = [[1,2,1]]                                              →  1
n = 2, k = 2, times = [[1,2,1]]                                              → -1
n = 4, k = 1, times = [[1,2,10],[1,3,1],[3,2,1],[2,4,1],[3,4,100]]            →  3

First row: from 2, nodes hear at 0, 1, 1, 2; the last is 2. Second: source plus one hop. Third: node 1 never hears. Fourth: two hops through 3 beat the direct 10 into 2; the last node hears at 3.

Note: BFS hop count is not a shortest-path strategy when weights vary. A FIFO queue settles the fewest hops, not the smallest latency. Unit weights collapse to hop count and BFS is then enough; this prompt does not promise that. The number to return is a latency (max dist[v]), not how many edges were used. Enumerating every path from k is also correct and worse than relaxing edges — do not DFS the path tree at the board unless they ask.

Relaxing every edge n−1 times is the honest brute force

dist[k] = 0, everyone else ∞. Then n - 1 rounds: for every edge u → v of weight w, if dist[u] + w is cheaper, write dist[v]. After that many rounds a shortest path of at most n - 1 edges has had a chance to propagate. Take the max, or -1 if anyone is still ∞. That is Bellman-Ford without a negative-cycle pass — this prompt promised non-negative w. Correct. O(n m).

int networkDelayTimeRelax(int[][] times, int n, int k) {
    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[k] = 0;
    for (int i = 0; i < n - 1; i++) {
        boolean changed = false;
        for (int[] e : times) {
            int u = e[0];
            int v = e[1];
            int w = e[2];
            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                changed = true;
            }
        }
        if (!changed) {
            break;
        }
    }
    int max = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == Integer.MAX_VALUE) {
            return -1;
        }
        max = Math.max(max, dist[i]);
    }
    return max;
}

At n = 12 this is a rounding error. On a dense mesh you paid a full edge scan per round for a question a min-heap answers by always expanding the closest unsettled node: what is the smallest known distance right now?

Min-heap of (dist, node): settle from k, then take the max

Build a directed adjacency list. Distances start at ∞ except dist[k] = 0. The frontier is a PriorityQueue min-heap of (dist, node). int[] is not Comparable — compare the distance slot, not reverseOrder(). Dijkstra already proved the first honest pop of a node is final when every weight is non-negative; do not re-derive decrease-key or sift.

Pop the smallest pair. If that distance is worse than dist[u], it is a stale re-push; skip it. Otherwise relax each outgoing u → v: a cheaper dist[v] is a new pair on the heap. Lazy re-push is the Java move. Then scan dist[1..n]: any leftover ∞ is -1; otherwise the answer is the max.

Walk the mixed-weight trap. Edges 1 → 2 weight 10, 1 → 3 weight 1, 3 → 2 weight 1, 2 → 4 weight 1, 3 → 4 weight 100. Source 1.

dist: 1=0  2=∞  3=∞  4=∞
pq:   (0,1)

pop (0,1)   settle 1
  relax 1→2  dist[2]=10   push (10,2)
  relax 1→3  dist[3]=1    push (1,3)
pq: (1,3), (10,2)

pop (1,3)   settle 3
  relax 3→2  dist[2]=2    push (2,2)    (10,2) still in the heap
  relax 3→4  dist[4]=101  push (101,4)
pq: (2,2), (10,2), (101,4)

pop (2,2)   settle 2
  relax 2→4  dist[4]=3    push (3,4)
pq: (3,4), (10,2), (101,4)

pop (3,4)   settle 4
pq: (10,2), (101,4)

pop (10,2)  stale (dist[2]=2)   skip
pop (101,4) stale (dist[4]=3)   skip

max(0, 2, 1, 3) = 3

BFS would have settled 2 on the first hop at cost 10 and reported 11. The heap waited for the cheaper 2. The Java is that walk:

int networkDelayTime(int[][] times, int n, int k) {
    List<List<int[]>> adj = new ArrayList<>(n + 1);
    for (int i = 0; i <= n; i++) {
        adj.add(new ArrayList<>());
    }
    for (int[] e : times) {
        adj.get(e[0]).add(new int[] { e[1], e[2] });
    }

    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[k] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    pq.offer(new int[] { 0, k });

    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int d = cur[0];
        int u = cur[1];
        if (d > dist[u]) {
            continue;
        }
        for (int[] edge : adj.get(u)) {
            int v = edge[0];
            int w = edge[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new int[] { dist[v], v });
            }
        }
    }

    int max = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == Integer.MAX_VALUE) {
            return -1;
        }
        max = Math.max(max, dist[i]);
    }
    return max;
}

Time is O(m log m) — each edge can push a heap pair, and a binary heap pays log per offer and poll. Usually written O(m log n). Space is O(n + m) for the adjacency lists, dist, and a heap that can grow to O(m) stale pairs. n is the node count; m is times.length. Index 0 is unused because labels start at 1.

Note: Guard the add: dist[u] is a real cost before you write dist[u] + w. Integer.MAX_VALUE + w wraps. The stale check is d > dist[u]; skipping it re-relaxes a worse pair. java.util.Stack is the wrong type. A FIFO ArrayDeque is BFS. This frontier is a min-heap.

What interviewers usually poke next

  • Cheapest Flights Within K Stops. There is a stop budget. Plain Dijkstra without the stop in the state is wrong: the cheapest path may use too many hops, and a costlier path with fewer stops can be the one that is allowed.
  • Min Cost to Connect All Points. That is an MST: cheapest way to link every point to every other, not shortest paths from one source. Dijkstra from k does not build that tree.
  • Negative weights. Dijkstra’s first pop is no longer final. Name Bellman-Ford and stop; this prompt promised non-negative w.
  • Stop at one destination. Then you may return when that node settles. This prompt needs every node, so drain the heap (or keep going until the remaining pops are stale) and then take the max.
  • n = 1, no edges, k isolated. One node already heard at time 0. A source with no outgoing edges still returns 0 if n = 1, and -1 if anyone else exists.

You are done with this problem when you can say, out loud, why hop-count BFS is wrong on mixed weights, why relaxing every edge n - 1 times is correct but O(n m), and why the answer is max dist[v] (or -1) rather than the distance to a single target.