Network Delay Time — Dijkstra Shortest Path from a Single Source

Problem Statement#

You are given a network of n nodes, labeled 1 through n, and a list of travel times as directed edges times[i] = [u, v, w], where u is the source node, v is the target node, and w is the time it takes for a signal to travel from u to v. We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Constraints:

• 1 <= k <= n <= 100
• 1 <= times.length <= 6000
• times[i].length == 3
• 1 <= u, v <= n, u != v
• 0 <= w <= 100
• All pairs (u, v) are unique.

Example 1:

Input:  times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Explanation: Signal leaves node 2. It reaches node 1 and 3 at time 1, then node 4 at time 2.
             All 4 nodes reached → answer is max(0, 1, 1, 2) = 2.

Example 2:

Input:  times = [[1,2,1]], n = 2, k = 1
Output: 1
Explanation: Only one edge; node 2 is reached at time 1. Both nodes reached → answer is 1.

Example 3:

Input:  times = [[1,2,1]], n = 2, k = 2
Output: -1
Explanation: Signal starts at node 2. There is no path to node 1, so return -1.

Why This Problem Matters#

Network Delay Time is the canonical single-source shortest path problem in disguise. Every FAANG interviewer uses it to check whether you can translate the textbook Dijkstra algorithm into clean code under time pressure. The problem also shows up embedded in larger design problems: given a distributed system, how long until all replicas receive an update? Given a network topology, which node is the bottleneck?

Beyond the interview, Dijkstra is the backbone of routing protocols (OSPF), map navigation (Google Maps), and game pathfinding (A* is Dijkstra with a heuristic). Understanding how to implement a min-heap Dijkstra efficiently — with lazy deletion instead of a decrease-key operation — is essential for competitive programming and systems design.

The pattern here also generalises naturally to problems like Cheapest Flights Within K Stops (add a constraint to the state), Shortest Path in a Grid with Obstacles (weighted BFS), and Path with Maximum Probability (negate weights and maximize).

The Core Insight#

The key insight is that "minimum time for all nodes to receive the signal" is equivalent to asking: what is the longest shortest path from node k to any other node?

Dijkstra's algorithm solves single-source shortest paths on non-negative weighted graphs in O(E log V). It works greedily: always finalize the node whose current tentative distance is smallest. Once a node is finalized, its shortest path is guaranteed correct — no future relaxation can improve it — because all edge weights are non-negative.

After running Dijkstra from k, you have the shortest distance to every reachable node. The signal arrives at all nodes at time equal to the maximum of those distances. If any node remains unreachable (distance = infinity), return -1.

The practical implementation uses a min-heap of (distance, node) pairs. When you pop a pair, if its distance is already worse than the best known, skip it (lazy deletion). Otherwise, relax all outgoing edges.

Visual Dry Run#

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

Adjacency list:

2 → [(1,1), (3,1)]
3 → [(4,1)]

Initial distances: {1: inf, 2: 0, 3: inf, 4: inf} Heap: [(0, 2)]

Final distances: {1:1, 2:0, 3:1, 4:2} Answer: max(1, 0, 1, 2) = 2

Common Mistakes#

1. Using BFS instead of Dijkstra. BFS finds shortest paths only in unweighted graphs. Here edges have different weights; BFS can finalize a node with a non-optimal distance because it does not account for edge weights. Always use a min-heap (priority queue) when edges are weighted.

2. Forgetting the stale-entry check. Because Python's heapq does not support decrease-key, you push duplicate entries. When you pop an entry, check if the popped distance is greater than the current best. If so, skip it. Omitting this check does not affect correctness (you will still re-relax correctly), but it blows up the time complexity from O(E log V) to O(E log E).

3. Off-by-one on node indexing. Nodes are labeled 1 to n, not 0 to n-1. Using a 0-indexed array causes either an array-out-of-bounds error or silently wrong results because index 0 is unused. Build your distance array with size n+1 and ignore index 0, or use a dictionary keyed by node label.

4. Checking all n+1 entries of a zero-indexed array. If you initialize dist = [inf] * (n+1), the final max(dist) will always return inf because dist[0] was never set to a real value. Either slice dist[1:] for the max, or initialize dist[0] to 0 and exclude it explicitly.

5. Returning max(dist.values()) without checking for unreachable nodes. If any node is not reachable from k, its distance remains infinity. max(dist.values()) returns float('inf'), which you must convert to -1. The check return ans if ans < float('inf') else -1 is easy to forget under interview pressure.

6. Not building the adjacency list — iterating over times directly for every node. Some candidates scan the entire times array for each node being relaxed. This turns the algorithm into O(V * E), eliminating the log-factor benefit of the heap. Always preprocess times into an adjacency list.

Solutions#

Python#

import heapq
from collections import defaultdict
 
class Solution:
    def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
        # Build adjacency list: node → list of (neighbor, weight)
        adj = defaultdict(list)
        for u, v, w in times:
            adj[u].append((v, w))
 
        # dist[node] = shortest known distance from k; start with infinity
        dist = {i: float('inf') for i in range(1, n + 1)}
        dist[k] = 0  # source is zero distance from itself
 
        # Min-heap of (distance, node); start from source with distance 0
        heap = [(0, k)]
 
        while heap:
            d, u = heapq.heappop(heap)  # always pop the closest unfinalized node
 
            # Stale entry: a shorter path to u was already found
            if d > dist[u]:
                continue
 
            # Relax each outgoing edge from u
            for v, w in adj[u]:
                new_dist = dist[u] + w
                if new_dist < dist[v]:          # found a shorter path to v
                    dist[v] = new_dist
                    heapq.heappush(heap, (dist[v], v))  # push updated distance
 
        # The signal reaches all nodes at time = max shortest distance
        ans = max(dist.values())
        return ans if ans < float('inf') else -1  # -1 if any node unreachable

JavaScript#

var networkDelayTime = function(times, n, k) {
    // Build adjacency list: node → [[neighbor, weight], ...]
    const adj = new Map();
    for (let i = 1; i <= n; i++) adj.set(i, []);
    for (const [u, v, w] of times) {
        adj.get(u).push([v, w]);
    }
 
    // dist[node] = shortest known distance from k
    const dist = new Array(n + 1).fill(Infinity);
    dist[k] = 0; // source is zero distance from itself
 
    // Min-heap implemented as a sorted array (for clarity in interviews)
    // In production use a proper priority queue library
    const heap = [[0, k]]; // [distance, node]
 
    // Simple min-heap helper: always sort after push (O(E log E) but interview-clear)
    const heapPush = (item) => {
        heap.push(item);
        heap.sort((a, b) => a[0] - b[0]); // keep min at front
    };
    const heapPop = () => heap.shift(); // remove and return smallest
 
    while (heap.length > 0) {
        const [d, u] = heapPop(); // closest unfinalized node
 
        // Stale entry: a shorter path to u was already finalized
        if (d > dist[u]) continue;
 
        // Relax each outgoing edge from u
        for (const [v, w] of adj.get(u)) {
            const newDist = dist[u] + w;
            if (newDist < dist[v]) {       // found shorter path to v
                dist[v] = newDist;
                heapPush([dist[v], v]);    // push updated distance
            }
        }
    }
 
    // Answer = max shortest distance among nodes 1..n
    let ans = 0;
    for (let i = 1; i <= n; i++) {
        if (dist[i] === Infinity) return -1; // node i unreachable
        ans = Math.max(ans, dist[i]);
    }
    return ans;
};

Complexity Analysis#

The Dijkstra min-heap approach is optimal. With E up to 6000 and V up to 100, even a naive O(V²) Dijkstra would work within constraints, but the heap version is the expected interview answer.

Follow-up Questions#

Q: What if edge weights can be negative? Dijkstra breaks with negative weights. Use Bellman-Ford instead: relax all edges V-1 times, O(V * E). If there is a negative cycle reachable from k, signal delay is undefined (infinitely fast loop).

Q: What if you only need to find the path length, not the path itself? Dijkstra already only computes distances. To reconstruct the actual path, maintain a prev array where prev[v] = u whenever you relax edge (u, v). Trace back from the target.

Q: How does this change if the graph is undirected? Add both directions to the adjacency list: adj[u].append((v,w)) and adj[v].append((u,w)). The rest of the algorithm is identical.

Q: What is the time complexity if you use a Fibonacci heap? O(E + V log V) — the decrease-key operation becomes O(1) amortized. In practice, binary heaps with lazy deletion are faster due to constant factors and cache locality.

This Pattern Solves#

• LC 743 — Network Delay Time (this problem)
• LC 787 — Cheapest Flights Within K Stops (Bellman-Ford variant)
• LC 1631 — Path With Minimum Effort (Dijkstra on grid)
• LC 1514 — Path with Maximum Probability (negate log-weights)
• LC 882 — Reachable Nodes in Subdivided Graph
• LC 505 — The Maze II (Dijkstra on grid)

Key Takeaways#

• Network Delay Time = Dijkstra's algorithm from source k; answer = max of all shortest distances
• Return -1 if any node's distance is still infinity after Dijkstra — it is unreachable
• Lazy deletion: Python's heapq has no decrease-key; push duplicates and skip stale entries when popping
• Dijkstra template: adjacency list + distance array initialized to infinity (source=0) + min-heap with (dist, node)
• Time O((V + E) log V) with a binary heap; Space O(V + E) for the graph and distances
• Only process a node the first time it is popped (skip if visited[node] already set)
• Every weighted-graph shortest-path interview problem is a variation of this Dijkstra template