Network Delay Time

Network Delay Time

What is this problem about?

The Network Delay Time problem gives you a directed weighted graph representing network nodes and signal travel times. A signal is sent from a source node. Find the minimum time for the signal to reach all nodes, or return -1 if any node is unreachable. This Network Delay Time coding problem is the canonical application of Dijkstra's algorithm for single-source shortest paths.

Why is this asked in interviews?

Microsoft, Meta, Amazon, Netflix, Google, and Bloomberg ask this as the standard Dijkstra's algorithm problem. It validates that candidates can implement single-source shortest paths cleanly on a directed graph with a min-heap. The shortest path, BFS, graph, DFS, and heap interview pattern is comprehensively demonstrated here.

Algorithmic pattern used

Dijkstra's algorithm. Build an adjacency list from the edge list. Initialize dist[source] = 0, all others = infinity. Use a min-heap: (distance, node). Process the node with minimum distance, relaxing all outgoing edges. When a shorter path is found, push the updated distance to the heap. After processing all reachable nodes, the answer is max(dist) if all nodes are reached, or -1 otherwise.

Example explanation

Nodes: 4, edges: [(2,1,1),(2,3,1),(3,4,1),(1,4,2)], source=2.

• dist[2]=0. Process 2: dist[1]=1, dist[3]=1.
• Process 1 (dist=1): dist[4] = min(∞, 1+2) = 3.
• Process 3 (dist=1): dist[4] = min(3, 1+1) = 2.
• Process 4 (dist=2). Max dist = max(1,0,1,2) = 2.

Common mistakes candidates make

• Using BFS instead of Dijkstra (BFS doesn't handle weighted edges).
• Not initializing all distances to infinity before processing.
• Returning n instead of the actual maximum distance.
• Not checking if all nodes are reachable (some dist values remain infinity).

Interview preparation tip

Network Delay Time is the textbook Dijkstra problem. Implement it until you can write it fluently from memory: adjacency list construction, min-heap initialization, relaxation loop, max-dist computation. Common follow-ups: "what if edges can be negative?" (Bellman-Ford), "what if you need all-pairs shortest paths?" (Floyd-Warshall). Being able to discuss these alternatives shows comprehensive graph knowledge.