Network Delay Time (LC 743)

Pattern: Dijkstra’s Shortest Path (Single-Source, Non-negative Weights) Difficulty: Medium Key Concept: Find the shortest delay from source k to every other node. The “delay” of the whole network is the maximum shortest delay among all reachable nodes. If any node is unreachable, return -1.

Problem Statement

You are given a list of travel times times[i] = [u, v, w] meaning a signal travels from node u to v in w time. There are n nodes labeled 1..n. From source k, return the time it takes for all nodes to receive the signal, or -1 if some node never receives it.

Example

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

---

1. Algorithm & Pseudocode

build adjacency list adj[u] = list of (v, w)
dist[1..n] = INF
dist[k] = 0
pq = min-heap on (dist, node)
pq.offer((0, k))
while pq not empty:
    (d, u) = pq.poll()
    if d > dist[u]: continue          // stale
    for (v, w) in adj[u]:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            pq.offer((dist[v], v))

answer = max(dist[1..n])
return answer == INF ? -1 : answer

---

2. Step-by-Step Analysis

Why Dijkstra Edge weights are positive (non-negative). The first time we pop a node from the heap, its dist is final — that’s the greedy invariant Dijkstra relies on.

Why the “stale entry” check d > dist[u] We may push a node multiple times as we find shorter paths. The first pop with the correct dist does the work; later (larger) pops should be skipped.

Why we want the max of dist The signal reaches all nodes after the slowest one — that’s the maximum shortest distance.

Edge case If any dist[v] remains INF, that node is unreachable → return -1.

ASCII Trace for times = [[2,1,1],[2,3,1],[3,4,1]], n=4, k=2

adj: 1→[], 2→[(1,1),(3,1)], 3→[(4,1)], 4→[]
dist: [_, INF, 0, INF, INF]

pop (0,2): relax 1→1, 3→1; push (1,1),(1,3)
pop (1,1): no neighbors
pop (1,3): relax 4→2; push (2,4)
pop (2,4): no neighbors

dist: [_, 1, 0, 1, 2]
max = 2 → return 2

---

3. Java Solution

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
        for (int[] t : times) adj.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;

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);  // (node, dist)
        pq.offer(new int[]{k, 0});

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int u = cur[0], d = cur[1];
            if (d > dist[u]) continue;
            for (int[] nb : adj.get(u)) {
                int v = nb[0], w = nb[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{v, dist[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: (O((V + E) \log V)) Space: (O(V + E))

---

4. The “Java vs. Others” Edge

• Subtraction comparator (a,b) -> a[1] - b[1] is fine here because times are bounded; use Integer.compare for risky ranges.
• We size arrays [n+1] to match the 1-indexed node labels — easier than off-by-one fixes.
• For negative weights or bounded-stops problems (LC 787), use Bellman-Ford or modified BFS instead — Dijkstra would be incorrect.

---

5. Complexity Summary

Approach	Time	Space	Notes
Dijkstra (heap)	(O((V+E) \log V))	O(V + E)	Default for non-negative weights
Bellman-Ford	(O(V \cdot E))	O(V)	Needed when negative edges are allowed