· By John Kavanagh

Network Delay Time in TypeScript: Why the Heap Matters

A utility pole and branching overhead wires silhouetted against a cloudy sky.
Image by Red Shuheart, licensed from Unsplash.

A route with fewer hops isn't necessarily quicker. One expensive connection can lose to three cheap ones, which is precisely where an ordinary breadth‑first traversal stops being enough.

Network Delay Time on LeetCode asks when a signal has reached every node in a directed network. Each connection has a travel time. We start at one node, find the earliest arrival at each of the others, and return the latest of those arrival times. If a node cannot receive the signal, the answer is -1.

I find this a useful introduction to Dijkstra's algorithm because the output exposes two separate decisions: minimise the journey to each destination, then take the maximum across those minimums. Adding all the distances would describe a rather different delivery service.


Decide What the Queue is Ordering

Imagine connections from node 1 to node 2 costing 9, from 1 to 3 costing 2, and from 3 to 2 costing 3. The direct route reaches node 2 at time 9; going through node 3 gets there at time 5. The whole network has received the signal after 5 units of time.

A breadth‑first queue processes by the number of connections taken. Dijkstra processes by the smallest arrival time discovered so far. That change is the reason for the priority queue. We aren't asking which node entered the queue first.

Each queued item is a pair: arrival time, then node. An adjacency list stores outgoing connections. The best array holds the cheapest arrival discovered for each node, initially Infinity everywhere except the starting node, whose distance is zero.

The signal can travel along different outgoing connections independently. There is no shared courier who must finish one delivery before starting another, and no instruction to visit every node on a single route.


Why Taking the Smallest Works

Suppose the smallest current arrival in the heap is time 5. Any route through a node whose earliest possible arrival is 7 already costs at least 7, before taking another connection. With non‑negative edge weights, continuing that route cannot bring the total below 5.

More formally, consider a hypothetical shorter path to the node we're about to remove. At the boundary between its already processed and unprocessed nodes, relaxing that connection would have put an arrival no greater than that shorter path into the heap. That contradicts our choice of the smallest queued arrival. The current distance is therefore final.

The non‑negative condition does actual work in that argument. This problem permits zero‑cost connections, which are fine. Negative weights would break the reasoning, so I wouldn't reuse this implementation for them.

When examining an outgoing connection, we add its weight to the current arrival. If that improves the destination's recorded distance, we update best and push the new pair. This is usually called relaxing an edge: we replace an overly generous upper bound with a tighter one.


A Small Heap, with No Hidden Library Requirement

My Kth Largest in a Stream article uses a heap to retain a useful subset of values. Here the heap orders pending arrivals. The parent must have an arrival time no greater than either child; the entire array does not need to be sorted.

Insertion moves an arrival upwards until its parent is no larger. Removal returns the root, then moves the last item down through the smaller child until the ordering is restored. Equal times need no special tie‑break because either node can be processed first.

type Arrival = readonly [time: number, node: number];

class MinArrivalHeap {
  private readonly items: Arrival[] = [];

  push = (arrival: Arrival): void => {
    let index = this.items.length;
    this.items.push(arrival);

    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);
      const parentArrival = this.items[parent]!;
      if (parentArrival[0] <= arrival[0]) break;
      this.items[index] = parentArrival;
      index = parent;
    }
    this.items[index] = arrival;
  };

  pop = (): Arrival | undefined => {
    const first = this.items[0];
    const last = this.items.pop();
    if (this.items.length === 0 || last === undefined) return first;

    let index = 0;
    while (index * 2 + 1 < this.items.length) {
      const left = index * 2 + 1;
      const right = left + 1;
      const child = right < this.items.length
        && this.items[right]![0] < this.items[left]![0] ? right : left;
      const childArrival = this.items[child]!;
      if (last[0] <= childArrival[0]) break;
      this.items[index] = childArrival;
      index = child;
    }
    this.items[index] = last;
    return first;
  };
}

The non‑null assertions follow the index checks: a parent exists when index > 0, and a left child exists whilst the loop condition holds. The right child is read only after its bound has been checked. These assertions express the heap invariant; they aren't a substitute for validating arbitrary external input.


Keep Old Entries, Then Recognise Them

There is one deliberately unglamorous shortcut. Improving a distance doesn't remove the old pair from the heap. In the earlier example, both [9, 2] and [5, 2] can be present. Updating an arbitrary heap item would require extra indexing machinery, so I push the improvement and leave the old pair alone.

When [9, 2] eventually comes out, best[2] is already 5. The equality check skips it. Stale entries are expected working data, not evidence that the heap has malfunctioned.

Only strict improvements are inserted. That also prevents a zero‑cost cycle from repeatedly queuing equal distances. The smallest current arrival is processed once; obsolete copies never scan its outgoing connections again.

const networkDelayTime = (times: number[][], n: number, k: number): number => {
  const neighbours: Array<Array<readonly [number, number]>> =
    Array.from({ length: n + 1 }, () => []);
  for (const edge of times) {
    const [from, to, weight] = edge as [number, number, number];
    neighbours[from]!.push([to, weight]);
  }

  const best: number[] = Array(n + 1).fill(Infinity);
  best[k] = 0;
  const pending = new MinArrivalHeap();
  pending.push([0, k]);

  let arrival: Arrival | undefined;
  while ((arrival = pending.pop()) !== undefined) {
    const [time, node] = arrival;
    if (time !== best[node]) continue;

    for (const [next, weight] of neighbours[node]!) {
      const candidate = time + weight;
      if (candidate >= best[next]!) continue;
      best[next] = candidate;
      pending.push([candidate, next]);
    }
  }

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

Use both code blocks together. The solution uses one‑based node labels because that is the problem's input format. Index zero is intentionally unused and excluded from the final maximum. Including it would leave an Infinity in the result for no good reason.

The tuple assertions reflect LeetCode's promised three‑number edge format. This function does not validate malformed edges or out‑of‑range labels. It builds a separate adjacency list and does not sort or mutate times.


Cost, Including the Untidy Heap Entries

Let V be the number of nodes and E the number of connections. Building the adjacency list and distance array costs O(V + E) time and space. Each reachable node's outgoing list is scanned once, and there can be up to E successful improvements.

Because this version retains stale arrivals, the heap can contain O(E) items. Its running time is O(V + E log(E + 1)), with O(V + E) auxiliary space. Writing O(V) for the heap would overlook the implementation choice we just made.

Under this problem's restriction of at most one edge per ordered node pair, the familiar O((V + E) log V) bound also describes the work for V greater than one. I prefer the first expression here because it explains the actual queue. For a dense, tiny graph, a simple array scan for the next node is also reasonable; a heap isn't compulsory ceremony.

Distances remain comfortably within JavaScript's exact integer range under the published limits. There are at most 100 nodes and edge weights are at most 100; a shortest route needs no positive‑cost cycle. Floating‑point weights in a different application would deserve a separate numerical discussion.


Test the Reason for the Algorithm

An unreachable node should produce -1. A zero‑cost chain should produce zero. A longer route with a cheaper total should beat an expensive direct edge. Most importantly, include a case where a later discovery improves a node that is already waiting in the heap.

My Weighted Graph Comparison Lab includes those cases, independent all‑pairs distance checks on small graphs, and an editable example that prints the stale arrival. It also tests heap operation sequences against a sorted‑array reference, including equal priorities and repeated removals from an empty heap.


Wrapping Up

The useful idea is the combination: best records the strongest distance claim we currently have, the heap chooses the next claim to examine, and non‑negative weights justify finalising it. The stale‑entry check keeps those responsibilities separate without complicating the heap.

That reasoning connects to my guide to choosing dynamic‑programming state: decide what information a future decision needs before choosing a data structure. My Cheapest Flights Within K Stops article follows that change: once a route has a stop limit, one distance per node no longer describes everything we need to know.

Downloadable Resource

  • Weighted Graph Comparison Lab

    Use this lab to compare heap‑based shortest paths with stop‑limited flights. Run independent small‑graph checks and inspect stale arrivals, cost rows, and two deliberately broken shortcuts.

    Download ZIP

Need a senior engineer involved?

I can work directly in the codebase, review the architecture, or support the team through delivery when the work needs more than extra hands.