Network Delay Time

Problem (restated)

A directed network of n nodes (1-indexed) and weighted edges times[i] = [u, v, w] (signal from u to v takes w). A signal starts at node k. Return the time for every node to receive it, or -1 if some node is unreachable.

Intuition

The time the last node hears the signal is the longest shortest-path from k. Weights are non-negative, so Dijkstra from k. Answer is max(dist[1..n]), or -1 if any dist is still infinite.

Approaches

/**
 * Toy PQ: sort + shift. Interview/production: binary heap, O((V+E) log V).
 */
export function networkDelayTime(times: number[][], n: number, k: number): number {
  const adj: [number, number][][] = Array.from({ length: n + 1 }, () => []);
  for (const [u, v, w] of times) adj[u]!.push([v, w]);
  const dist = new Array<number>(n + 1).fill(Infinity);
  dist[k] = 0;
  const pq: [number, number][] = [[0, k]];
  while (pq.length) {
    pq.sort((a, b) => a[0]! - b[0]!);
    const [d, u] = pq.shift()!;
    if (d > dist[u]!) continue;
    for (const [v, w] of adj[u]!) {
      if (d + w < dist[v]!) {
        dist[v] = d + w;
        pq.push([dist[v]!, v]);
      }
    }
  }
  let ans = 0;
  for (let i = 1; i <= n; i++) {
    if (dist[i] === Infinity) return -1;
    ans = Math.max(ans, dist[i]!);
  }
  return ans;
}

/**
 * Toy PQ: sort + shift. Interview/production: binary heap, O((V+E) log V).
 */
export function networkDelayTime(times: number[][], n: number, k: number): number {
  const adj: [number, number][][] = Array.from({ length: n + 1 }, () => []);
  for (const [u, v, w] of times) adj[u]!.push([v, w]);
  const dist = new Array<number>(n + 1).fill(Infinity);
  dist[k] = 0;
  const pq: [number, number][] = [[0, k]];
  while (pq.length) {
    pq.sort((a, b) => a[0]! - b[0]!);
    const [d, u] = pq.shift()!;
    if (d > dist[u]!) continue;
    for (const [v, w] of adj[u]!) {
      if (d + w < dist[v]!) {
        dist[v] = d + w;
        pq.push([dist[v]!, v]);
      }
    }
  }
  let ans = 0;
  for (let i = 1; i <= n; i++) {
    if (dist[i] === Infinity) return -1;
    ans = Math.max(ans, dist[i]!);
  }
  return ans;
}

Template connection

Plain Dijkstra: min-heap by distance, relax on pop, skip stale entries. LC 1976 is the same loop plus path counts.

Reflection

• Dijkstra from k with a min-heap of (time, node). The first pop of a node is its shortest time. The answer is the latest finite time.
• Any node still unreachable is −1. There are no negative weights. A later, larger time for the same node is a stale pop.
• n = 1 answers 0. No edges and n > 1 answers −1.