Network Delay Time LeetCode 743 — Dijkstra

LeetCode 743 — Network Delay Time — models a network of n nodes labeled 1 to n connected by directed weighted edges. You send a signal from a source node k and must determine the minimum time required for all nodes to receive the signal. If any node cannot be reached, return -1.

Each edge is represented as a tuple (u, v, w) meaning a directed link from node u to node v with travel time w. Since the graph is directed, the edge from u to v does not imply an edge from v to u. Edge weights are positive integers, which is the crucial property that makes Dijkstra's algorithm applicable.

The answer is the maximum shortest-path distance from k to any node. If even one node is unreachable — meaning no directed path exists from k to that node — the entire network cannot be notified and you return -1.

Standard BFS finds the shortest path by number of hops — it explores nodes level by level, treating each edge as having equal cost. In an unweighted graph this works perfectly: the first time BFS visits a node is always via the fewest edges. But network delay time uses weighted edges where shorter hop count does not mean shorter travel time.

Consider a graph where node k connects to node A with weight 1 and to node B with weight 100, and node B connects to node A with weight 1. BFS would visit A directly (1 hop, cost 1) and then B (1 hop, cost 100). But wait — the path k → B → A costs 101, so BFS correctly prioritizes the direct edge to A here. The failure mode is subtler: when there are two paths of different hop counts to the same node but different weights, BFS always picks the shorter-hop path even if it is heavier.

Dijkstra's algorithm fixes this by always processing the node with the current minimum known distance, regardless of hop count. It uses a min-heap (priority queue) to efficiently retrieve the closest unvisited node at each step, making it BFS with a priority queue instead of a plain queue.

The algorithm begins by building an adjacency list from the edge list. For each node u, store all (neighbor, weight) pairs reachable from u. This lets you look up all outgoing edges from any node in O(degree) time rather than scanning the full edge list.

Initialize all distances to infinity except dist[k] = 0 for the source. Push (0, k) into the min-heap — a tuple of (distance, node). While the heap is non-empty, pop the entry with the smallest distance. If this node has already been visited (finalized), skip it. Otherwise mark it visited, then for each neighbor push (dist[node] + weight, neighbor) into the heap if the new distance is smaller than the recorded distance.

After the heap empties, dist contains the shortest path from k to every reachable node. Unreachable nodes retain their infinity distance. Return the maximum of all distances, or -1 if any distance is still infinity.

The correctness of Dijkstra's algorithm rests on a simple greedy invariant: when a node is popped from the min-heap, its recorded distance is the true shortest path from the source. This claim seems surprising at first — how can we be sure no shorter path will be discovered later?

The proof is by induction. The source has distance 0 and is trivially correct. When we pop the next node u with distance d, suppose there were a shorter path through some unvisited node v. Since v is unvisited, dist[v] ≥ d (otherwise v would have been popped before u). Any path through v to u costs at least dist[v] + 0 ≥ d, and with positive edge weights it can only be larger. So no shorter path through an unvisited node can exist.

This is why Dijkstra requires non-negative edge weights. If a negative edge existed, a longer-looking path could suddenly become shorter after traversing it, breaking the invariant that popping from the heap finalizes the distance.

After running Dijkstra from source k, you have the shortest path distance from k to every node in the graph. The minimum time for all nodes to receive the signal is the time it takes the last node to receive it — which is the maximum among all shortest path distances.

To check if all nodes are reachable, simply verify that no distance remains at infinity (or whatever sentinel value you used for unreachable nodes). If any node is unreachable, return -1. Otherwise return the maximum distance.

In implementations using a visited set, nodes that were never popped from the heap were never finalized — they are unreachable. You can check visited.size() == n (for 1-indexed nodes, n total nodes) to verify full coverage before returning the maximum distance.

In Python, use heapq with (distance, node) tuples. Build the adjacency list as a defaultdict of lists. Initialize distances with float('inf') and set dist[k] = 0. Push (0, k) and loop until the heap is empty. Use a visited set to skip already-finalized nodes. At the end, return max(dist.values()) if len(dist) == n else -1.

In Java, use PriorityQueue<int[]> with a comparator (a, b) -> a[0] - b[0]. Build the adjacency list as List<List<int[]>>. Initialize a dist int array with Integer.MAX_VALUE, set dist[k-1] = 0 (converting to 0-indexed). After the heap empties, find the max of dist[] — if it equals Integer.MAX_VALUE, return -1, otherwise return the max.

Both implementations run in O((V+E) log V) time and O(V+E) space, where V = n nodes and E = number of edges. The heap can contain at most E entries in the worst case (one per edge relaxation), so the log factor is log E which is bounded by log V^2 = 2 log V.

Network Delay Time is the canonical Dijkstra problem on LeetCode. Swim in Rising Water (LC 778) is structurally identical — minimize the maximum edge weight on any path — and uses Dijkstra with the heap keyed by max edge weight instead of sum. Cheapest Flights Within K Stops (LC 787) adds a constraint on number of hops, requiring a modified Bellman-Ford or Dijkstra with state (node, stops_remaining).

Shortest Path in Binary Matrix (LC 1091) uses unweighted BFS (Dijkstra degenerates to BFS when all weights are equal). Path With Minimum Effort (LC 1631) again uses Dijkstra with the heap keyed by the maximum effort (edge weight) along the path — another min-max variant. All of these share the adjacency list + heap pattern.

For graphs with negative edges, study Bellman-Ford (LC 743 variant with negative weights) and SPFA. For all-pairs shortest paths, study Floyd-Warshall. Building intuition across the Dijkstra family — single-source, min-max, k-stops — makes graph problems significantly more tractable in interviews.