Network Delay Time: A Step-by-Step Interview Walkthrough

Jun 7

13 min read

Network Delay Time is the problem interviewers use to find out whether you understand why Dijkstra's algorithm exists, not just how to type it out. On the surface it looks like the BFS shortest-path problems you've already solved — a graph, a source, "find the shortest time to reach everything." But there's one detail that changes everything: the edges have different weights. That single difference breaks BFS, and the candidates who don't understand why will reach for BFS, get a subtly wrong answer, and not know it. The candidates who understand that unequal edge weights invalidate BFS's core assumption know to reach for Dijkstra instead. The signal here is whether you can tell weighted shortest path from unweighted shortest path, and whether you know why the distinction forces a different algorithm.

Weighted single-source shortest path is one of the most-used algorithms in production systems. Network routing protocols (OSPF, IS-IS) compute shortest paths through networks where links have different latencies or costs. GPS navigation finds fastest routes where roads have different travel times. Logistics systems compute cheapest shipping routes. Game pathfinding navigates terrain where different tiles cost different amounts to cross. Any time you're finding the cheapest or fastest way through a network where the steps have unequal costs, you're solving exactly this problem — and Dijkstra (or one of its relatives) is the tool.

Problem Statement

You are given a directed, weighted graph representing a network.

times[i] = [u, v, w] means a signal takes w time to travel from node u to node v.
There are n nodes labeled from 1 to n.
A signal is sent from node k.

Return the minimum time it takes for all nodes to receive the signal. If it's impossible for all nodes to receive it, return -1.

Example:

times = [[2,1,1],[2,3,1],[3,4,1]],

n = 4,

k = 2

result → 2 (the signal reaches node 4 last, at time 2, via 2→3→4).

1. Clarify Requirements Before Jumping Into Code

Before writing a single line, we should restate the problem in our own words and ask the kinds of questions that would change our approach.

Input: a list of weighted directed edges, the number of nodes n, and a source node k. Output: the time for the signal to reach every node, or -1 if some node is unreachable.

Details to clarify:

Is the graph directed? Yes — a signal from u to v doesn't imply one from v to u. This affects how we build the adjacency list.
Are edge weights positive? Yes — this matters enormously, as we'll see. Dijkstra requires non-negative weights.
Are nodes 1-indexed? Yes — a small detail, but it affects array sizing and loop bounds.
What exactly are we returning — a path, or a time? Just a single time value.
What time represents "all nodes received it"? The signal spreads in parallel along all paths, so "all received" happens at the moment the last node receives it — which is the maximum of the shortest arrival times.

It's important to make sure we understand the required output. "Time for all nodes to receive the signal" sounds like it might be a sum or a total, but that's not quite right. Each node receives the signal as soon as the fastest path reaches it; the whole network is "done" when the slowest of those fastest arrivals happens. So we first find the shortest path to every node, then take the maximum of those paths.

2. Identify the Category of the Question

A few signals jump out:

We have a graph with a single source (k).
We want the shortest distance from that source to every other node.
The edges have weights — different costs.

That combination — single source, shortest paths to all nodes, weighted edges — is the fingerprint of single-source shortest path on a weighted graph. And when the weights are non-negative, the canonical algorithm is Dijkstra's. Same family as any "cheapest/fastest route from one point to everywhere" problem. The weight detail is what separates this from the BFS shortest-path family (Word Ladder and friends), and recognizing that separation is the whole game.

3. Brute Force Solution

Let's think about the naive approach to understand the problem. We could try to enumerate every path from k to each node, keep the shortest for each, and then take the maximum.

for each node v:
    explore every path from k to v
    shortestTime[v] = minimum total weight over all those paths
return max(shortestTime)

The number of paths in a graph can be exponential — paths can wind through cycles, take detours, and overlap heavily. Enumerating them all is infeasible. Even a DFS with memoization struggles here, because the "best" answer for a node can change depending on the accumulated weight along the path that reached it, and that path-dependence makes naive memoization incorrect.

The brute force teaches us what we need: a way to compute, for every node, the single shortest distance from k, without enumerating paths. The challenge is the weights — they're why we can't just count hops.

4. Brainstorm More Solutions

Step 1: Why can't we just use BFS?

This is the central question, so let's take it seriously rather than skipping to Dijkstra.

BFS finds shortest paths beautifully — in unweighted graphs. Recall why it works there: BFS explores nodes in waves of increasing hop-count, so the first time it reaches a node, it's via the fewest hops, which (when every edge costs the same) is the cheapest path. The correctness depends entirely on one assumption: every edge costs the same, so "fewest edges" equals "lowest total cost."

Now look at our graph. Edges have different weights. The moment that's true, "fewest hops" and "lowest cost" can diverge. BFS commits to the first arrival, and with unequal weights, the first arrival (fewest hops) isn't necessarily the cheapest. So BFS gives wrong answers here.

That's not a minor inconvenience — it's a fundamental mismatch. We need an algorithm that explores by accumulated cost, not by hop count.

Step 2: What would fix BFS?

The idea behind BFS is a good one, so rather than abandoning it completely, let's see if there's a way we can modify the approach to make it work. BFS's strength is that it finalizes a node's distance the first time it reaches it, and that finalization is correct because it always processes nodes in order of distance. That sounds pretty similar to what we want here too, but the problem is that BFS only measures "distance" in hops.

So what if we kept that "process in order of distance, finalize on first arrival" structure, but instead of counting hops, we modified the algorithm so that we're measuring distance by accumulated weight instead of hop count? What would need to change in order to make that work?

Instead of a plain FIFO queue (which gives us hop-order), we'd need something that always hands us the node with the smallest total accumulated cost discovered so far. If we always expand the cheapest-reachable node next, then when we pop a node for the first time, no cheaper path to it can exist — because any alternative path would have to go through some node we haven't expanded yet, which by definition has a higher accumulated cost.

That "always expand the cheapest-known node next" is the key modification. And the data structure that gives us the minimum-cost item efficiently is a min-heap (priority queue), ordered by accumulated distance. Swap BFS's FIFO queue for a min-heap keyed on distance, and we have Dijkstra's algorithm.

Step 3: The mechanics of Dijkstra

We've decided on the core idea — always expand the cheapest-known node next, using a min-heap to find it. Now let's reason out the bookkeeping that idea requires.

First, we need to remember the best distance we've found to each node so far, since that's one of the requirements of the problem. So let's keep a dist[] array to store best distance to each node.

At the start, we've found a path to exactly one node — the source k, which is zero away from itself — and we know nothing about any other node yet. We'll represent "no path found to this node yet" as infinity. So dist[k] = 0 and every other entry starts at infinity. As the algorithm runs, these infinities get replaced by real distances whenever we discover a route.

Second, we need to know which node to expand next: the unexpanded node with the smallest known distance. That's exactly what a min-heap gives us cheaply. We seed it with (k, 0) — the source at distance zero, the only node we currently know how to reach.

Now the loop. We pop the cheapest node from the heap and ask: "from here, can I improve any of my neighbors' distances?" For each outgoing edge to a neighbor, the cost of reaching that neighbor through the current node is dist[node] + weight. If that total is less than the neighbor's currently recorded distance, we've just found a better route to the neighbor than anything we knew before — so we update dist[neighbor] to the smaller value and push the neighbor onto the heap so it'll get expanded later in turn.

That update step is the engine of the whole algorithm, and it has a name: relaxation. The intuition behind the word is that each dist[] entry is an upper bound on the true shortest distance — our best guess so far, which may be too high. Each time we find a cheaper route, we "relax" that bound downward, closer to the truth.

Then we repeat — pop the cheapest, relax its edges, push improved neighbors — until the heap is empty, meaning there are no more nodes whose distances could still improve.

Step 4: Two consequences worth nailing down

Two details fall out of the "always expand the cheapest node" rule that are easy to miss.

First, a node can appear in the heap multiple times — we push it again every time we find a shorter route, so older, longer entries linger. When we pop an entry whose distance is larger than the node's current best (poppedDistance > dist[node]), it's stale: we've already found something better, so we skip it. That one-line check keeps us from reprocessing nodes through paths we've already improved upon.

Second, this whole approach depends on non-negative weights. "First pop is final" only holds if distances grow as we move outward; a negative edge could make a later path cheaper than one we already locked in, breaking the guarantee. If a problem allows negative edges, Dijkstra is the wrong tool — that's Bellman-Ford's job.

Step 5: Translating the answer

Once Dijkstra finishes, dist[v] holds the shortest time for the signal to reach each node v. Now we map that back to what the problem asked:

If any node still has distance infinity, it was never reached — the signal can't get there — so return -1.
Otherwise, the signal reaches every node, and the whole network is "done" at the moment the last node gets it. That's the maximum value in dist[].

So the final answer is max(dist[1..n]), unless some node is unreachable, in which case it's -1.

Step 6: Walk through the example

Let's trace times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2. Adjacency: 2→1 (w1), 2→3 (w1), 3→4 (w1).

dist = [_, ∞, 0, ∞, ∞] (index 0 unused). Heap: [(2, 0)].
Pop (2, 0). Relax 2→1: dist[1] = 1, push (1, 1). Relax 2→3: dist[3] = 1, push (3, 1). Heap: [(1,1), (3,1)].
Pop (1, 1). Node 1 has no outgoing edges. Nothing to relax.
Pop (3, 1). Relax 3→4: dist[4] = 2, push (4, 2). Heap: [(4,2)].
Pop (4, 2). No outgoing edges. Heap empty.

Final dist: node 1 → 1, node 2 → 0, node 3 → 1, node 4 → 2. All reached. Max is 2. Answer: 2. Correct — node 4 receives the signal last, at time 2.

Step 7: Complexity

Let's derive the cost rather than quote it, since the reasoning is what transfers to other heap-based algorithms.

Start with the heap operations, because that's where the work concentrates. Every time we relax an edge and find an improvement, we push an entry onto the heap. How many pushes can happen? At most one per edge — each directed edge gives at most one chance to improve its target's distance and trigger a push. So the heap holds at most O(e) entries over the algorithm's lifetime, where e is the number of edges. Each push and each pop on a heap of size O(e) costs O(log e) time. Since e is at most n², log e is O(log n), so we can write each heap operation as O(log n).

Now count the operations. We pop entries until the heap empties — O(e) pops, each O(log n). And across the whole run, we examine each edge a constant number of times when relaxing (once per time we pop its source node), contributing O(e) edge examinations. Add the O(n) to initialize the distance array and the O(e) to build the adjacency list. Putting it together, the dominant term is the heap work: O(e) operations at O(log n) each, giving O((n + e) log n) time. (The n appears because in the worst case we touch every node and every edge.)

For space, we account for what we store. The adjacency list holds every edge once: O(n + e). The distance array is O(n). The heap, as we noted, can hold up to O(e) entries. So total space is O(n + e) — linear in the size of the graph.

The transferable takeaway is this: for heap-based graph algorithms, the time almost always comes out to "(number of heap operations) × (log of heap size)." Identify how many things get pushed and popped — usually bounded by edges or nodes — and multiply by the log factor. That single framing handles Dijkstra, Prim's MST, and most other priority-queue-driven graph algorithms.

5. Discuss Trade-Offs Between Solutions

Approach	Time	Space	When I'd use it
Brute-force path enumeration	Exponential	High	Never — paths explode combinatorially
BFS	O(n + e)	O(n)	Never here — gives wrong answers on weighted edges
Dijkstra (min-heap)	O((n + e) log n)	O(n)	My default for non-negative weighted shortest path
Bellman-Ford	O(n × e)	O(n)	If edges could be negative — slower but handles negatives

Dijkstra is the right answer for this problem because the weights are non-negative. BFS is on the table only for unweighted graphs; the moment weights differ, it's incorrect, not just suboptimal. Bellman-Ford is the fallback if negative weights are possible, at a higher time cost.

6. Pseudocode

build adjacency list from times (directed, weighted)

dist[] = infinity for all nodes
dist[k] = 0
minHeap = [(k, 0)]            # (node, distanceSoFar), ordered by distance

while heap not empty:
    (node, time) = heap.pop()        # smallest distance available
    if time > dist[node]: continue   # stale entry — already improved

    for each (neighbor, weight) in adjacency[node]:
        newTime = time + weight
        if newTime < dist[neighbor]:
            dist[neighbor] = newTime
            heap.push((neighbor, newTime))

if any dist[node] is infinity: return -1
return max(dist[1..n])

7. Edge Cases

Things to verify before claiming we're done:

Disconnected node (unreachable from k) → its distance stays infinity → return -1. ✓
Single-node graph where k is that node → distance 0, max is 0. ✓
Source can't reach some nodes (directed edges point the wrong way) → those stay infinity → return -1. ✓
Multiple edges between the same pair of nodes → relaxation naturally keeps the cheapest; no special handling. ✓
Cycles → Dijkstra handles them fine because non-negative weights mean revisiting never improves a finalized distance.
Large weights → no overflow concern for typical inputs, but worth keeping in mind for adversarial cases (using long if weights and path lengths could exceed int).

The unreachable-node case is the one that triggers the -1 return. Checking for any remaining infinity in the distance array is what distinguishes "reached everything" from "some node is stranded."

8. Full Code

import java.util.*;

public class NetworkDelayTime {

    public static int networkDelayTime(int[][] times, int n, int k) {
        // Build directed, weighted adjacency list 
        // (nodes are 1-indexed)
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] t : times) {
            // {neighbor, weight}
            graph.get(t[0]).add(new int[]{t[1], t[2]});  
        }

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

        // Min-heap ordered by accumulated distance — 
        // always expand cheapest node
        PriorityQueue<int[]> pq =
            new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.add(new int[]{k, 0});

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int node = curr[0];
            int time = curr[1];

            // Stale entry: we already found a shorter path
            if (time > dist[node]) continue;

            for (int[] edge : graph.get(node)) {
                int next = edge[0];
                int weight = edge[1];

                // Relax: is going through `node` cheaper 
                // than the best known path so far?
                if (dist[node] + weight < dist[next]) {
                    dist[next] = dist[node] + weight;
                    pq.add(new int[]{next, dist[next]});
                }
            }
        }

        // The network is "done" when the last node receives the 
        // signal — the maximum of all shortest distances. 
        // Infinity means unreachable.
        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;
    }
}

9. Test the Code

// Standard propagation
int[][] t1 = {{2,1,1},{2,3,1},{3,4,1}};
System.out.println(networkDelayTime(t1, 4, 2));  // 2

// Simple reachability
int[][] t2 = {{1,2,1}};
System.out.println(networkDelayTime(t2, 2, 1));  // 1

// Unreachable node (source can't reach node 1)
int[][] t3 = {{1,2,1}};
System.out.println(networkDelayTime(t3, 2, 2));  // -1

// Single node, no edges needed
int[][] t4 = {};
System.out.println(networkDelayTime(t4, 1, 1));  // 0

// Two paths to the same node — the cheaper one wins
int[][] t5 = {{1,2,10},{1,3,1},{3,2,2}};
System.out.println(networkDelayTime(t5, 3, 1));  // 3 (1→3→2 costs 3, beats direct 1→2 at 10)

// Cycle present — Dijkstra handles it
int[][] t6 = {{1,2,1},{2,3,1},{3,1,1},{3,4,1}};
System.out.println(networkDelayTime(t6, 4, 1));  // 3 (1→2→3→4)

These hit the meaningful cases: standard propagation, simple reachability, an unreachable node (the -1 case), a single node, the crucial "two paths, cheaper wins" case that BFS would get wrong, and a graph with a cycle. The t5 test is the one that proves we needed Dijkstra and not BFS — BFS would return 10 for node 2 instead of the correct 3.

10. Key Lessons

BFS finds shortest paths only when all edges have equal weight. The moment edge weights differ, "fewest hops" and "lowest cost" diverge, and BFS becomes incorrect — not just slower. Recognizing weighted vs. unweighted is the first fork in any shortest-path problem.
Dijkstra is BFS with the FIFO queue swapped for a min-heap ordered by accumulated cost. Understanding it as that specific modification — "process the cheapest-known node next instead of the fewest-hops node" — makes it something you can reconstruct, not just memorize.
The "first time we pop a node, its distance is final" guarantee is what makes Dijkstra correct, and it depends on non-negative weights. If weights can be negative, that guarantee breaks and you need Bellman-Ford instead. Always check the sign of the weights before choosing.
Skip stale heap entries with a if poppedDistance > dist[node]: continue check. Because we push a node every time we improve its distance, the heap accumulates outdated entries; skipping them keeps the algorithm efficient.
Read what the problem actually asks for and map it back to your computed values. Here, "time for all nodes to receive the signal" is the maximum of the shortest distances, and "impossible" is any remaining infinity. The algorithm computes shortest paths; translating those into the problem's answer is a separate, deliberate step.
For heap-based graph algorithms, the time complexity almost always comes out to "(number of heap operations) × (log of heap size)." Identify how many things get pushed and popped — usually bounded by edges or nodes — and multiply by the log factor.

The thing that makes Network Delay Time click isn't Dijkstra's code — it's understanding why BFS fails here and what specifically Dijkstra changes to fix it. Once you see that the whole difference is "expand by accumulated cost, not by hop count," Dijkstra stops being a memorized incantation and becomes an obvious adaptation of BFS to weighted graphs. That understanding is what lets you choose correctly the next time a shortest-path problem hides unequal weights in its setup.

Good Luck and Happy Coding!