Network Delay Time

1. Problem & Core Objective

Given n network nodes labelled 1 to n, a list of directed edges times[i] = [u, v, w] meaning a signal travels from u to v in w time, and a starting node k, return the time for all nodes to receive the signal. Return -1 if some node is unreachable.

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

Constraints: 1 <= k <= n <= 100 · 1 <= times.length <= 6000 · 1 <= w <= 100 · all weights positive

What's actually being tested: Dijkstra's algorithm, and specifically why BFS doesn't work here. The answer being the maximum of all shortest paths — rather than a single shortest path — is a small twist that checks you understood what's being computed.

2. First-Principles Thought Process

Why BFS fails

BFS finds the path with the fewest edges. Here edges have different weights, so the fewest hops is not the cheapest.

A two-hop route costing 20 and a two-hop route costing 2 look identical to BFS. It would report the wrong arrival time.

Dijkstra is BFS with a different queue

Replace the FIFO queue with a min-heap ordered by accumulated cost. Then nodes are finalised in order of increasing distance from the source, exactly as BFS finalises them in order of hop count.

That's the cleanest way to hold the relationship: same algorithm, different ordering, and the uniform-cost case makes them coincide.

Why the first pop is final

When a node is popped with cost d, every unfinalised node has cost >= d (heap property). Since all weights are positive, any alternative route to this node must pass through an unfinalised node and therefore cost >= d already, plus more.

So d cannot be improved — the node is done.

This argument requires positive weights. With a negative edge, a longer detour could reduce the total, and the first pop would be wrong. The constraint w >= 1 is what licenses Dijkstra here.

The answer is the maximum, not the minimum

"Time for all nodes to receive the signal" means waiting for the slowest one. So compute the shortest path to every node, then take the maximum of those.

And if any node is still at infinity, it's unreachable → return -1.

That's the twist: Dijkstra's usual output is one distance; here you need all of them and then an aggregate.

3. Solution Paths

Approach 1 — Bellman-Ford

public int networkDelayTime(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++)                     // n-1 rounds
        for (int[] t : times) {
            if (dist[t[0]] == Integer.MAX_VALUE) continue;
            dist[t[1]] = Math.min(dist[t[1]], dist[t[0]] + t[2]);
        }

    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 O(V · E) = 100 × 6000 = 6 × 10^5 · Space O(V)

Counter-questions on this approach

⭐ "Why n − 1 rounds?"

Because a shortest path in a graph with no negative cycles uses at most n − 1 edges — any more would repeat a node, and removing that loop can't make it longer with non-negative weights.

Each round guarantees that all shortest paths using one more edge are found, so after n − 1 rounds every shortest path is complete.

⭐ "It's fast enough here. Why prefer Dijkstra?"

Bellman-Ford is O(V · E) and Dijkstra is O(E log V) — here 6 × 10^5 versus about 6000 × 7 = 4 × 10^4, so roughly 15× fewer operations.

Bellman-Ford's advantage is handling negative weights, which this problem doesn't have. Paying O(V · E) for a capability you don't need is the objection.

"Why the dist[t[0]] == MAX_VALUE guard?"

Because MAX_VALUE + w overflows to a large negative number, which would then look like an excellent distance and corrupt everything downstream. The guard skips relaxing from a node that hasn't been reached yet.

It's the same sentinel-overflow discipline as elsewhere: Integer.MAX_VALUE as infinity is only safe if you never do arithmetic on it.

Approach 2 — Dijkstra with a min-heap (optimal)

public int networkDelayTime(int[][] times, int n, int k) {
    Map<Integer, List<int[]>> adj = new HashMap<>();          // node -> {neighbour, weight}
    for (int[] t : times)
        adj.computeIfAbsent(t[0], x -> new ArrayList<>()).add(new int[]{t[1], t[2]});

    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[k] = 0;

    PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(e -> e[0]));
    heap.offer(new int[]{0, k});                               // {cost, node}

    while (!heap.isEmpty()) {
        int[] top = heap.poll();
        int cost = top[0], node = top[1];
        if (cost > dist[node]) continue;                       // stale entry

        for (int[] nb : adj.getOrDefault(node, List.of())) {
            int next = nb[0], newCost = cost + nb[1];
            if (newCost < dist[next]) {                        // relax
                dist[next] = newCost;
                heap.offer(new int[]{newCost, next});
            }
        }
    }

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

Trace — times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2:

dist = [_, 1, 0, 1, 2], maximum = 2 ✓

• Time O(E log V) · Space O(V + E)

Counter-questions on this approach

⭐ "Why is the first pop of a node final?"

When a node is popped with cost d, the heap property says every remaining entry has cost >= d. Any alternative route to this node must go through some unfinalised node, whose own cost is already >= d, and then add a positive edge weight on top.

So no alternative can beat d. The node is done, and never needs revisiting.

That argument depends entirely on weights being positive. With a negative edge a detour could reduce the total, and the invariant collapses — which is why Bellman-Ford exists.

⭐ "Why if (cost > dist[node]) continue; rather than a visited set?"

It's lazy deletion. A node can be offered to the heap several times as better routes are discovered, and outdated entries stay in the heap because PriorityQueue.remove(Object) is O(n).

Comparing the popped cost against the current best identifies a stale entry in O(1). A boolean[] visited would work equally well; this version reuses dist and needs no extra array.

⭐ "Why is the answer the maximum rather than a single distance?"

Because the question asks when all nodes have received the signal, which is when the slowest one does. Each dist[i] is the earliest that node can be reached, so the overall completion time is max(dist[i]).

It's a small twist but it checks you understood that Dijkstra computes distances to every node, not just to one target — the single-target version just stops early.

"Why does an unreachable node give -1?"

Its distance stays Integer.MAX_VALUE because no relaxation ever reached it. The problem says the signal never arrives, so the answer is -1 rather than infinity.

"Why is dist sized n + 1?"

Nodes are labelled 1 to n, not 0 to n − 1. Sizing it n would throw on node n. Index 0 is unused.

"Could cost + nb[1] overflow?"

Only from MAX_VALUE, and that can't happen — a node is only popped after dist[node] was set to a real value. The unreached nodes are never expanded. That's the same protection the Bellman-Ford guard provides explicitly.

"What's the real complexity?"

O(E log V) — each edge can cause at most one heap insertion, and each heap operation is O(log V)... more precisely O(log E), but since E <= V², log E <= 2 log V, so they're the same up to a constant. At E = 6000 that's about 4 × 10^4.

Comparison

4. Why the Optimal Wins

BFS is simply wrong: it orders by hop count, and the fewest hops isn't the cheapest when edges differ.

Bellman-Ford is correct but does O(V · E) work to gain negative-weight support that the constraints rule out. Dijkstra exploits positivity to finalise each node on its first pop, never revisiting — roughly 15× fewer operations here.

The framing worth keeping:

Dijkstra is BFS with the queue replaced by a min-heap ordered by accumulated cost. The first pop of a node is final — but only because all weights are positive.

And the twist: the answer is max(dist[i]), because "all nodes received it" means waiting for the slowest.

5. Java Prerequisites

Weighted adjacency list

Map<Integer, List<int[]>> adj = new HashMap<>();
adj.computeIfAbsent(from, x -> new ArrayList<>()).add(new int[]{to, weight});

Dijkstra skeleton

PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(e -> e[0]));
heap.offer(new int[]{0, source});
while (!heap.isEmpty()) {
    int[] top = heap.poll();
    if (top[0] > dist[top[1]]) continue;        // lazy deletion
    for (each neighbour) if (newCost < dist[next]) { dist[next] = newCost; heap.offer(...); }
}

Integer.MAX_VALUE as infinity — never do arithmetic on it. Guard before adding, or ensure unreached nodes are never expanded.

1-indexed nodes — size arrays n + 1.

6. Interview Communication Guide

Clarifying questions: Are weights positive (yes — this is what licenses Dijkstra, so confirm it)? Are nodes 1-indexed (yes)? Is the graph directed (yes)? What if some node is unreachable (return -1)? Can there be parallel edges (possible; the relaxation handles them)?

The pitch

"BFS is out, because it orders by edge count and the edges have different weights — a two-hop route costing 20 and a two-hop route costing 2 look identical to it.

Dijkstra is the fix, and the cleanest way to see it is that it's BFS with the queue replaced by a min-heap ordered by accumulated cost. Same algorithm, different ordering — and when all weights are equal the two coincide.

The key invariant: the first time a node is popped, its cost is final. When it's popped with cost d, every remaining heap entry costs at least d, and any alternative route must pass through an unfinalised node and then add a positive weight on top. So nothing can beat d.

That argument depends entirely on weights being positive — with a negative edge a detour could reduce the total, and you'd need Bellman-Ford instead. So I'd confirm the constraint rather than assume it.

I use lazy deletion — if (cost > dist[node]) continue; — because a node gets offered to the heap multiple times as better routes appear, and removing stale entries from a PriorityQueue is O(n). Skipping them on arrival is O(1).

The twist is the answer: the question asks when all nodes have the signal, which is when the slowest does. So I take max(dist[i]) over every node, and return -1 if any is still at infinity.

O(E log V) ≈ 4 × 10^4 here. Bellman-Ford would also work at O(V · E) = 6 × 10^5, but that buys negative-weight support the constraints rule out."

Edge cases to volunteer:

Name the single-node case and the unreachable one. The first must return 0 rather than crashing on an empty heap loop; the second is the -1 path that a solution focused on the max can forget.

7. Follow-Up Questions — Modified Constraints

⭐ "What if some weights were negative?"

Dijkstra breaks — the first-pop-is-final invariant fails, since a negative edge could reduce a total after the node was finalised. Use Bellman-Ford at O(V · E), which also detects negative cycles: run one extra round and if any distance still improves, a negative cycle exists and shortest paths are undefined.

⭐ "Return the path to the slowest node, not just the time."

Track a parent[] updated on each successful relaxation, then walk back from the node with the maximum distance. O(V) extra space, no complexity change.

"What if you needed all-pairs shortest paths?"

Run Dijkstra from every node — O(V · E log V) — or use Floyd-Warshall at O(V³). At n = 100 that's 10^6, so Floyd-Warshall is simpler and competitive. It also handles negative edges (not cycles).

"What if the graph were undirected?"

Add both directions when building the adjacency list. Dijkstra is unchanged — it never assumes direction.

"What if n were 10^5 with 10^6 edges?"

Still fine for Dijkstra at O(E log V) ≈ 2 × 10^7. But Map<Integer, List<int[]>> boxes every key and allocates per node — a flat CSR array representation would be far leaner. Bellman-Ford at 10^11 would be hopeless.

"Find the shortest path to a single target rather than all nodes."

Return as soon as the target is popped, since its distance is final at that moment. A meaningful saving when the target is close — and it's also why bidirectional Dijkstra helps for point-to-point queries.