Network Delay Time

Examples

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

From node 2, nodes 1 and 3 are reached at time 1, and node 3 forwards to node 4 at time 2 - so all nodes are reached by time 2.

Input: times = [[1,2,1]], n = 2, k = 1
Output: 1

Node 2 receives the signal from node 1 after 1 unit of time.

Input: times = [[1,2,1]], n = 2, k = 2
Output: -1

There's no edge leaving node 2, so node 1 can never receive the signal.

Constraints

• 1 <= n <= 100

• 1 <= times.length <= 6000

• 1 <= ui, vi <= n

• ui != vi

• 0 <= wi <= 100

• There are no duplicate edges and no self-loops.

Approach

This is a single-source shortest path problem: find the shortest time from k to every other node, then the answer is the maximum of those shortest times (since the whole network isn't informed until the farthest node gets the signal). If any node is unreachable, the answer is -1.

Because all travel times are non-negative, Dijkstra's algorithm applies directly: repeatedly pick the not-yet-finalized node with the smallest known distance, finalize it, and relax (try to improve) the distances of its neighbors. A min-heap keeps picking that "smallest known distance" node efficient.

A simpler but slower alternative is Bellman-Ford-style relaxation: repeatedly loop over every edge, relaxing distances, for up to n - 1 rounds - correct for any edge weights (even negative ones), just slower here since it doesn't take advantage of the non-negative weights the way Dijkstra's does.

Solutions

Bellman-Ford Style Relaxation

Start with the distance to k at 0 and every other node at infinity. Repeat, up to n - 1 times: go through every edge [u, v, w], and if the known distance to u plus w is smaller than the currently known distance to v, update it. After enough rounds, every shortest distance is finalized (a shortest path uses at most n - 1 edges). The answer is the largest finite distance, or -1 if any node is still unreachable.

function networkDelayTime(times, n, k) {
  const dist = new Array(n + 1).fill(Infinity);
  dist[k] = 0;

  for (let round = 0; round < n - 1; round++) {
    let updated = false;
    for (const [u, v, w] of times) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        updated = true;
      }
    }
    if (!updated) break;
  }

  let maxDist = 0;
  for (let node = 1; node <= n; node++) {
    if (dist[node] === Infinity) return -1;
    maxDist = Math.max(maxDist, dist[node]);
  }
  return maxDist;
}

Time: O(n * E), where E is the number of edges, from up to n - 1 rounds each scanning every edge · Space: O(n) for the distance array

Optimal - Dijkstra's Algorithm

Build an adjacency list from the edges. Use a min-heap of [distance, node] pairs, starting with [0, k]. Repeatedly pop the smallest-distance entry; if that node's shortest distance isn't already finalized, finalize it and push [newDistance, neighbor] for every neighbor whose distance improves. Because the heap always surfaces the closest not-yet-finalized node next, once a node is popped and finalized its distance can never improve again - this is what makes Dijkstra faster than blindly relaxing every edge repeatedly.

function networkDelayTime(times, n, k) {
  const graph = new Map();
  for (const [u, v, w] of times) {
    if (!graph.has(u)) graph.set(u, []);
    graph.get(u).push([v, w]);
  }

  const dist = new Array(n + 1).fill(Infinity);
  dist[k] = 0;

  // Simple binary min-heap keyed on distance.
  const heap = [[0, k]];
  function push(item) {
    heap.push(item);
    let i = heap.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (heap[parent][0] <= heap[i][0]) break;
      [heap[parent], heap[i]] = [heap[i], heap[parent]];
      i = parent;
    }
  }
  function pop() {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      while (true) {
        let smallest = i;
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        if (left < heap.length && heap[left][0] < heap[smallest][0]) smallest = left;
        if (right < heap.length && heap[right][0] < heap[smallest][0]) smallest = right;
        if (smallest === i) break;
        [heap[smallest], heap[i]] = [heap[i], heap[smallest]];
        i = smallest;
      }
    }
    return top;
  }

  const visited = new Array(n + 1).fill(false);
  while (heap.length > 0) {
    const [d, node] = pop();
    if (visited[node]) continue;
    visited[node] = true;

    const neighbors = graph.get(node) || [];
    for (const [next, weight] of neighbors) {
      if (d + weight < dist[next]) {
        dist[next] = d + weight;
        push([dist[next], next]);
      }
    }
  }

  let maxDist = 0;
  for (let node = 1; node <= n; node++) {
    if (dist[node] === Infinity) return -1;
    maxDist = Math.max(maxDist, dist[node]);
  }
  return maxDist;
}

Time: O(E log E), where E is the number of edges, from each edge potentially pushing one heap entry · Space: O(n + E) for the adjacency list, distance array, and heap