Network Delay Time
Asked at Netflix
Problem
Given a network of N nodes with weighted directed edges and a source node, find the time it takes for a signal to reach all nodes. Return the minimum time needed, or -1 if some nodes are unreachable. This is the classic single-source shortest path problem on a weighted graph.
Asked At
| Company | Difficulty | |
|---|---|---|
| Netflix | MEDIUM | View all Netflix questions → |
How to Think About It
Build an adjacency list representation of the weighted directed graph
Use Dijkstra's algorithm with a min-heap to greedily find shortest paths
Initialize distances to infinity except source which is 0
Process nodes in order of increasing distance from source
The answer is the maximum distance among all reachable nodes
Optimal Approach
Model the network as a weighted directed graph using an adjacency list. Apply Dijkstra's algorithm starting from the source node. Use a min-heap (priority queue) to always process the node with the smallest known distance next. For each node popped from the heap, relax all its outgoing edges: if the distance to a neighbor through the current node is shorter than the known distance, update it and push to the heap. After processing, the answer is the maximum distance across all nodes. If any node remains at infinity, return -1.
What Trips People Up in Real Interviews
Confirm the graph is directed and edges have non-negative weights
Ask if there are negative edge weights (would need Bellman-Ford instead)
Clarify that the answer is the max of all shortest paths, not the sum
Mention BFS works for unweighted graphs but Dijkstra is needed here
Discuss time complexity: O((V+E) log V) with a binary heap
Solution Code
import heapq
from collections import defaultdict
class Solution:
def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {}
min_heap = [(0, k)]
while min_heap:
d, node = heapq.heappop(min_heap)
if node in dist:
continue
dist[node] = d
for neighbor, weight in graph[node]:
if neighbor not in dist:
heapq.heappush(min_heap, (d + weight, neighbor))
return max(dist.values()) if len(dist) == n else -1Frequently Asked Questions
What is the Network Delay Time problem?
Given a network of N nodes with weighted directed edges and a source node, find the time it takes for a signal to reach all nodes. Return the minimum time needed, or -1 if some nodes are unreachable. This is the classic single-source shortest path problem on a weighted graph.
How do you solve Network Delay Time?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Network Delay Time?
Network Delay Time is asked at Netflix. It is a medium difficulty problem.
What are common mistakes on Network Delay Time?
- Confirm the graph is directed and edges have non-negative weights
- Ask if there are negative edge weights (would need Bellman-Ford instead)
- Clarify that the answer is the max of all shortest paths, not the sum
- Mention BFS works for unweighted graphs but Dijkstra is needed here
- Discuss time complexity: O((V+E) log V) with a binary heap