8.6 Dijkstra (Weighted Shortest Path)

Demo: Network Delay Time — LC 743 (Medium — Google/Amazon High)

Statement (Demo): A network has n nodes and weighted edges times[i] = [u, v, w]. A signal starts at node k. Return the time until every node receives it, or -1 if some node never does. Example: times=[[2,1,1],[2,3,1],[3,4,1]], n=4, k=2 → 2 | ⚡ n ≤ 100

Approach: Min-heap of [distance, node] from the source. Pop the closest node and relax its edges — push a new entry whenever a distance improves. When a stale entry pops, the d > dist[u] check skips it. (MinHeap class → 6.1.)

function networkDelayTime(times, n, k) {
  const adj = Array.from({ length: n + 1 }, () => []);
  for (const [u, v, w] of times) adj[u].push([v, w]);
  const dist = new Array(n + 1).fill(Infinity);
  dist[k] = 0;
  const heap = new MinHeap((a, b) => a[0] - b[0]); // [dist, node]
  heap.push([0, k]);
  while (heap.size) {
    const [d, u] = heap.pop();
    if (d > dist[u]) continue; // stale entry
    for (const [v, w] of adj[u]) {
      if (d + w < dist[v]) {
        dist[v] = d + w;
        heap.push([dist[v], v]);
      }
    }
  }
  const ans = Math.max(...dist.slice(1));
  return ans === Infinity ? -1 : ans;
}

Complexity: Time O(E log V), Space O(V + E)