4.21.3 — Network Delay Time

LeetCode 743 · Medium

The problem

A signal starts at node k and travels along directed edges with travel times. Return how long until every node has received it, or -1 if some node never does.

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

Times are positive.

The pattern

The answer is the largest of the shortest paths from k to every other node — the signal is finished when the slowest recipient has it.

So this is single-source shortest path on a weighted graph with non-negative weights, which is Dijkstra's algorithm.

BFS is not enough here, and understanding why is the point of the problem. BFS finds the path with the fewest edges, which is only the shortest path when every edge costs the same. With weights, a two-edge route can easily be cheaper than a one-edge route.

How Dijkstra works, in one idea

Always finalise the closest unfinished node.

Keep a frontier of nodes you can reach and the cheapest known cost to each. Repeatedly take the cheapest, declare its distance final, and relax its outgoing edges — that is, offer its neighbours a route through it.

Why is finalising safe? Because all weights are non-negative. If the cheapest unfinished node is at distance d, any other route to it would have to pass through some other unfinished node, which is at distance ≥ d already, and adding a non-negative edge can only make it worse. So no cheaper route can exist.

That argument is exactly where negative weights break it, and it is worth being able to say. With a negative edge, going "further away" first can come back cheaper, so finalising early is wrong. Then you need Bellman-Ford — which is 4.21.6.

The solution

Python

import heapq
from collections import defaultdict

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        adj = defaultdict(list)
        for u, v, w in times:
            adj[u].append((v, w))

        dist = {}                              # finalised distances
        heap = [(0, k)]                        # (cost so far, node)

        while heap:
            cost, node = heapq.heappop(heap)
            if node in dist:
                continue                       # already finalised — stale entry

            dist[node] = cost                  # first pop is the shortest

            for nei, w in adj[node]:
                if nei not in dist:
                    heapq.heappush(heap, (cost + w, nei))

        return max(dist.values()) if len(dist) == n else -1

TypeScript

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

  const dist = new Map<number, number>();
  const heap = new MinHeap<[number, number]>((e) => e[0]);
  heap.push([0, k]);

  while (heap.size) {
    const [cost, node] = heap.pop()!;
    if (dist.has(node)) continue;

    dist.set(node, cost);

    for (const [nei, w] of adj.get(node) ?? []) {
      if (!dist.has(nei)) heap.push([cost + w, nei]);
    }
  }

  return dist.size === n ? Math.max(...dist.values()) : -1;
}

The first time a node pops, that is its shortest distance. Everything else follows from this. It is why dist[node] = cost needs no comparison and no update.

if node in dist: continue is lazy deletion, the same as in 4.21.2. A node can be pushed several times with different costs; the cheapest surfaces first and the rest are skipped. Heaps cannot update a stored priority, so you leave stale copies and ignore them.

len(dist) == n is the reachability check. Any node the signal never reaches is simply absent from the map.

max(dist.values()) is the answer, because the signal is done when the last node receives it.

Trace

times = [[2,1,1],[2,3,1],[3,4,1]], k = 2.

Pop (0, 2) → dist[2] = 0. Push (1, 1) and (1, 3).

Pop (1, 1) → dist[1] = 1. No outgoing edges.

Pop (1, 3) → dist[3] = 1. Push (2, 4).

Pop (2, 4) → dist[4] = 2.

All four nodes reached; the maximum is 2. ✓

Complexity

O(E \log V) with a binary heap. Each edge can cause one push, and each push or pop is O(\log V).

Space O(V + E).

For a dense graph, scanning an array for the minimum instead of using a heap gives O(V^2), which is better when E \approx V^2. With a Fibonacci heap the bound is O(E + V \log V), which is better in theory and slower in practice because of its constants. Naming these is enough.

Dijkstra compared with the alternatives

	handles	complexity	use when
BFS	unweighted	O(V + E)	every edge costs the same
Dijkstra	non-negative weights	O(E \log V)	the usual case
Bellman-Ford	negative weights	O(V \cdot E)	negatives, or a hop limit
Floyd-Warshall	all pairs	O(V^3)	small graph, many queries
0-1 BFS	weights of only 0 or 1	O(V + E)	a deque replaces the heap

Choosing correctly is most of the marks on any shortest-path question. Read the weights before choosing.

The trap worth knowing

Adding a constant to every weight to remove negatives does not work. If you add 5 to each edge, a three-edge path gains 15 while a one-edge path gains 5, so paths with more edges are penalised and the shortest path can change.

This gets suggested in interviews often, and being able to give that one-line counterexample is a reliable way to show you understand what Dijkstra actually assumes.

Where this goes next

• Path with Minimum Effort, Swim in Rising Water — Dijkstra where the path cost is a maximum along the route rather than a sum. 4.21.4.
• Cheapest Flights Within K Stops — Dijkstra breaks because of the hop limit; Bellman-Ford handles it. 4.21.6.
• Path with Maximum Probability — multiply probabilities instead of adding costs, and use a max-heap.
• Real routing — OSPF runs Dijkstra over a map of the network flooded to every router. Chapter 5.3.2 covers it, and it is a good thing to mention.

What the interviewer will push on

"Why not BFS?" Weighted edges. BFS optimises the number of hops, not the cost.

"Why is it safe to finalise the closest node?" Non-negative weights mean no cheaper route can exist through a node that is already further away.

"What breaks with negative weights?" Exactly that argument. Then say Bellman-Ford.

"Could you just add a constant to make the weights positive?" No — give the counterexample.

"What are the duplicate heap entries?" Lazy deletion; heaps cannot update a priority.

"When would you use Floyd-Warshall instead?" Small graph, all-pairs distances wanted.

One thing to volunteer: name the assumption before writing the code. "All weights are non-negative, so Dijkstra applies; if any were negative I would need Bellman-Ford." That sentence answers the two most likely follow-ups in advance.

Next: 4.21.4 Swim in Rising Water — Dijkstra where the cost of a path is its maximum rather than its sum.