Network Delay Time
Problem
Given a list of travel times as directed edges times where times[i] = (u, v, w) represents the time w to travel from node u to node v, and given the number of nodes n and a starting node k, return the time it takes for all nodes to receive the signal sent from node k. If it is impossible for all nodes to receive the signal, return -1.
- 1 ≤ k ≤ n ≤ 100
- 1 ≤ times.length ≤ 6000
- times[i].length == 3
- 1 ≤ u, v ≤ n
- u != v
- 0 ≤ w ≤ 100
- All pairs (u, v) are unique.
Example
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 22Starting from node 2, the signal reaches node 1 in 1 unit of time and node 3 in 1 unit of time. From node 3, the signal reaches node 4 in 1 additional unit of time. The longest time among all nodes to receive the signal is 2, which is the answer.
Approach
Straightforward Solution
A brute-force approach would attempt to explore all paths from k to every node, which is computationally expensive and inefficient, especially with cycles and multiple paths.
Core Observation
The problem reduces to finding the shortest path from a single source node k to all other nodes in a weighted directed graph, where edge weights represent travel times.
Path to Optimal
Recognizing the problem as a shortest path problem on a weighted graph suggests using Dijkstra's algorithm. The key insight is to use a priority queue (min-heap) to always explore the next closest node, ensuring that once a node is visited, the shortest path to it is finalized. This avoids redundant work and guarantees optimality.
Optimal Approach
Build an adjacency list from the input edges for efficient neighbor lookup. Use a min-heap initialized with the starting node k at distance 0. Repeatedly pop the node with the smallest tentative distance, skip if already visited, and update the maximum time seen. For each neighbor, if unvisited, push the cumulative distance into the heap. After processing, if all nodes are visited, return the maximum distance; otherwise, return -1.
Time
O(E log V)
Each edge is processed at most once when its source node is popped from the heap, and each heap operation takes O(log V) time, where V is the number of nodes and E is the number of edges.
Space
O(V + E)
The adjacency list stores all edges (O(E)), and the heap and visited set store nodes (O(V)). This space is necessary to represent the graph and track visited nodes.
Pattern Spotlight
Dijkstra's Algorithm (Single-Source Shortest Path)
Always expand the closest unvisited node next using a min-heap to guarantee that once a node is visited, its shortest path is finalized, enabling efficient and correct shortest path computation.
Solution
| 1 | import collections
|
| 2 | import heapq
|
| 3 |
|
| 4 | class Solution:
|
| 5 | def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
|
| 6 | edges = collections.defaultdict(list)
|
| 7 | for u, v, w in times:
|
| 8 | edges[u].append((v, w))
|
| 9 |
|
| 10 | min_heap = [(0, k)]
|
| 11 | visit = set()
|
| 12 | t = 0
|
| 13 | while min_heap:
|
| 14 | w1, n1 = heapq.heappop(min_heap)
|
| 15 | if n1 in visit:
|
| 16 | continue
|
| 17 | visit.add(n1)
|
| 18 | t = max(t, w1)
|
| 19 |
|
| 20 | for n2, w2 in edges[n1]:
|
| 21 | if n2 not in visit:
|
| 22 | heapq.heappush(min_heap, (w1 + w2, n2))
|
| 23 |
|
| 24 | return t if len(visit) == n else -1 |
| 1 | import java.util.*; |
| 2 | |
| 3 | class Solution { |
| 4 | public int networkDelayTime(int[][] times, int n, int k) { |
| 5 | Map<Integer, List<int[]>> edges = new HashMap<>(); |
| 6 | for (int[] time : times) { |
| 7 | edges.computeIfAbsent(time[0], x -> new ArrayList<>()).add(new int[]{time[1], time[2]}); |
| 8 | } |
| 9 | |
| 10 | PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0])); |
| 11 | minHeap.offer(new int[]{0, k}); |
| 12 | Set<Integer> visit = new HashSet<>(); |
| 13 | int t = 0; |
| 14 | |
| 15 | while (!minHeap.isEmpty()) { |
| 16 | int[] curr = minHeap.poll(); |
| 17 | int w1 = curr[0], n1 = curr[1]; |
| 18 | if (visit.contains(n1)) { |
| 19 | continue; |
| 20 | } |
| 21 | visit.add(n1); |
| 22 | t = Math.max(t, w1); |
| 23 | |
| 24 | List<int[]> neighbors = edges.getOrDefault(n1, Collections.emptyList()); |
| 25 | for (int[] neighbor : neighbors) { |
| 26 | int n2 = neighbor[0], w2 = neighbor[1]; |
| 27 | if (!visit.contains(n2)) { |
| 28 | minHeap.offer(new int[]{w1 + w2, n2}); |
| 29 | } |
| 30 | } |
| 31 | } |
| 32 | |
| 33 | return visit.size() == n ? t : -1; |
| 34 | } |
| 35 | } |
| 1 | #include <vector> |
| 2 | #include <queue> |
| 3 | #include <unordered_map> |
| 4 | #include <unordered_set> |
| 5 | #include <algorithm> |
| 6 | |
| 7 | using namespace std; |
| 8 | |
| 9 | class Solution { |
| 10 | public: |
| 11 | int networkDelayTime(vector<vector<int>>& times, int n, int k) { |
| 12 | unordered_map<int, vector<pair<int, int>>> edges; |
| 13 | for (const auto& time : times) { |
| 14 | edges[time[0]].emplace_back(time[1], time[2]); |
| 15 | } |
| 16 | |
| 17 | priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> min_heap; |
| 18 | min_heap.emplace(0, k); |
| 19 | unordered_set<int> visit; |
| 20 | int t = 0; |
| 21 | |
| 22 | while (!min_heap.empty()) { |
| 23 | auto [w1, n1] = min_heap.top(); |
| 24 | min_heap.pop(); |
| 25 | if (visit.count(n1)) { |
| 26 | continue; |
| 27 | } |
| 28 | visit.insert(n1); |
| 29 | t = max(t, w1); |
| 30 | |
| 31 | for (const auto& [n2, w2] : edges[n1]) { |
| 32 | if (!visit.count(n2)) { |
| 33 | min_heap.emplace(w1 + w2, n2); |
| 34 | } |
| 35 | } |
| 36 | } |
| 37 | |
| 38 | return visit.size() == n ? t : -1; |
| 39 | } |
| 40 | }; |
| 1 | var networkDelayTime = function(times, n, k) { |
| 2 | const edges = new Map(); |
| 3 | for (const [u, v, w] of times) { |
| 4 | if (!edges.has(u)) edges.set(u, []); |
| 5 | edges.get(u).push([v, w]); |
| 6 | } |
| 7 | |
| 8 | const minHeap = []; |
| 9 | // Helper functions for minHeap |
| 10 | function heapPush(heap, val) { |
| 11 | heap.push(val); |
| 12 | let i = heap.length - 1; |
| 13 | while (i > 0) { |
| 14 | let parent = Math.floor((i - 1) / 2); |
| 15 | if (heap[parent][0] <= heap[i][0]) break; |
| 16 | [heap[parent], heap[i]] = [heap[i], heap[parent]]; |
| 17 | i = parent; |
| 18 | } |
| 19 | } |
| 20 | function heapPop(heap) { |
| 21 | const top = heap[0]; |
| 22 | const end = heap.pop(); |
| 23 | if (heap.length > 0) { |
| 24 | heap[0] = end; |
| 25 | let i = 0; |
| 26 | while (true) { |
| 27 | let left = 2 * i + 1; |
| 28 | let right = 2 * i + 2; |
| 29 | let smallest = i; |
| 30 | if (left < heap.length && heap[left][0] < heap[smallest][0]) smallest = left; |
| 31 | if (right < heap.length && heap[right][0] < heap[smallest][0]) smallest = right; |
| 32 | if (smallest === i) break; |
| 33 | [heap[i], heap[smallest]] = [heap[smallest], heap[i]]; |
| 34 | i = smallest; |
| 35 | } |
| 36 | } |
| 37 | return top; |
| 38 | } |
| 39 | |
| 40 | heapPush(minHeap, [0, k]); |
| 41 | const visit = new Set(); |
| 42 | let t = 0; |
| 43 | |
| 44 | while (minHeap.length > 0) { |
| 45 | const [w1, n1] = heapPop(minHeap); |
| 46 | if (visit.has(n1)) continue; |
| 47 | visit.add(n1); |
| 48 | t = Math.max(t, w1); |
| 49 | |
| 50 | const neighbors = edges.get(n1) || []; |
| 51 | for (const [n2, w2] of neighbors) { |
| 52 | if (!visit.has(n2)) { |
| 53 | heapPush(minHeap, [w1 + w2, n2]); |
| 54 | } |
| 55 | } |
| 56 | } |
| 57 | |
| 58 | return visit.size === n ? t : -1; |
| 59 | }; |
Step-by-Step Solution
Build the Graph as an Adjacency List for Efficient Neighbor Lookup
| 6 | edges = collections.defaultdict(list)
|
| 7 | for u, v, w in times:
|
| 8 | edges[u].append((v, w))
|
Objective
To transform the edge list into a structure that allows quick access to neighbors and their travel times.
Key Insight
An adjacency list maps each node to a list of its outgoing edges, enabling O(1) average-time access to neighbors during traversal. This structure is essential for efficient graph algorithms like Dijkstra's, avoiding repeated scanning of the entire edge list.
Interview Quick-Check
Core Logic
Using a defaultdict of lists to store edges allows efficient iteration over neighbors during the shortest path search.
Common Pitfalls & Bugs
Forgetting to build the adjacency list or using an inefficient data structure can lead to slower neighbor lookups and increased time complexity.
Initialize Min-Heap and Visited Set to Track Exploration State
| 10 | min_heap = [(0, k)]
|
| 11 | visit = set()
|
| 12 | t = 0
|
Objective
To prepare the data structures that manage the order of node exploration and prevent revisiting nodes.
Key Insight
The min-heap prioritizes nodes with the smallest current distance, ensuring the algorithm explores nodes in order of increasing distance from the source. The visited set prevents processing a node more than once, which is crucial because the first time a node is popped from the heap, its shortest path is finalized.
Interview Quick-Check
Core Logic
The min-heap stores tuples of (distance, node), enabling efficient retrieval of the closest unvisited node.
State & Boundaries
The visited set ensures each node is processed only once, preventing infinite loops and redundant work.
Process Nodes in Order of Increasing Distance and Update Maximum Delay
| 13 | while min_heap:
|
| 14 | w1, n1 = heapq.heappop(min_heap)
|
| 15 | if n1 in visit:
|
| 16 | continue
|
| 17 | visit.add(n1)
|
| 18 | t = max(t, w1)
|
Objective
To iteratively explore the graph, finalizing shortest paths and tracking the longest time needed for the signal to reach any node.
Key Insight
By popping the node with the smallest tentative distance, the algorithm finalizes the shortest path to that node. Updating the maximum delay with the current node's distance captures the longest shortest path from the source to any reachable node. This step embodies the core of Dijkstra's algorithm.
Interview Quick-Check
Core Logic
Processing nodes in ascending order of distance guarantees that the first time a node is visited, its shortest path is known.
Common Pitfalls & Bugs
Skipping nodes already visited is essential to avoid processing stale entries in the heap that do not represent the shortest path.
State & Boundaries
Updating the maximum delay at each visited node ensures the final answer reflects the longest shortest path.
Push Neighboring Nodes into the Heap with Updated Distances
| 20 | for n2, w2 in edges[n1]:
|
| 21 | if n2 not in visit:
|
| 22 | heapq.heappush(min_heap, (w1 + w2, n2))
|
Objective
To explore all reachable neighbors by adding them to the heap with their cumulative distances from the source.
Key Insight
For each neighbor of the current node, if it has not been visited, the algorithm pushes the sum of the current node's distance and the edge weight into the heap. This ensures that all possible paths are considered, but only the shortest path will be finalized due to the heap's ordering and the visited set.
Interview Quick-Check
Core Logic
Adding neighbors with updated distances to the heap allows the algorithm to explore all potential shortest paths in order.
Common Pitfalls & Bugs
Failing to check if a neighbor is already visited before pushing can lead to redundant processing and incorrect results.
Return the Maximum Delay if All Nodes Are Visited, Otherwise Return -1
| 24 | return t if len(visit) == n else -1 |
Objective
To determine if the signal reached all nodes and return the appropriate result.
Key Insight
If the number of visited nodes equals n, it means all nodes are reachable from the source, and the maximum delay recorded is the answer. Otherwise, some nodes are unreachable, and the problem requires returning -1 to indicate impossibility.
Interview Quick-Check
Core Logic
Comparing the size of the visited set to n confirms whether all nodes received the signal.
State & Boundaries
Returning -1 when not all nodes are visited correctly handles disconnected graphs.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
w1, n1 = heapq.heappop(min_heap)Pop the node with the smallest tentative distance from the heap.
Extracting the closest unvisited node is the core operation of Dijkstra's algorithm, guaranteeing that the shortest path to this node is finalized.
return t if len(visit) == n else -1Return the maximum delay if all nodes are visited; otherwise, return -1.
This conditional return correctly handles disconnected graphs by returning -1 when some nodes are unreachable, and otherwise returns the longest shortest path as the answer.
min_heap = [(0, k)]Initialize a min-heap with a tuple representing the starting node k at distance 0.
The min-heap prioritizes nodes by their current shortest known distance from the source, enabling Dijkstra's algorithm to explore nodes in order of increasing distance.
continueMark the current node as visited.
Adding the node to the visited set finalizes its shortest path and prevents future reprocessing.
if n2 not in visit:Push the neighbor into the heap with the updated cumulative distance.
Adding neighbors with their cumulative distances ensures that all possible paths are considered, but the heap ordering guarantees shortest paths are finalized first.
edges = collections.defaultdict(list)Initialize a default dictionary to store adjacency lists for each node.
Using a defaultdict of lists allows efficient storage and retrieval of all outgoing edges from each node, which is essential for graph traversal algorithms like Dijkstra's.
edges[u].append((v, w))Append the destination node and edge weight to the adjacency list of the source node.
This step constructs the graph's adjacency list, enabling quick access to neighbors and their travel times during traversal.
visit = set()Create a set to track visited nodes.
The visited set prevents revisiting nodes, ensuring each node's shortest path is finalized exactly once and avoiding infinite loops.
if n1 in visit:Skip processing if the node has already been visited.
Skipping visited nodes prevents redundant work and ensures correctness by not revisiting nodes whose shortest paths are already known.
for n2, w2 in edges[n1]:For each neighbor, check if it has not been visited.
Only unvisited neighbors are candidates for updated shortest paths and should be added to the heap for future exploration.
while min_heap:Start a loop that continues until the min-heap is empty.
This loop processes nodes in order of increasing distance, ensuring that the shortest paths are found efficiently.
visit.add(n1)Update the maximum delay with the current node's distance if it is larger.
Maintaining the maximum delay ensures the algorithm captures the longest shortest path from the source to any reachable node.
t = max(t, w1)Iterate over all neighbors and their edge weights of the current node.
Exploring neighbors is necessary to propagate the shortest path calculations through the graph.
t = 0Initialize a variable to track the maximum delay time.
Tracking the maximum delay allows the algorithm to determine the longest shortest path from the source to any node, which is the problem's answer.
for u, v, w in times:Iterate over each edge in the input times list.
Processing each edge is necessary to build the adjacency list representation of the graph.
Test Your Understanding
Why does Dijkstra's algorithm guarantee that the first time a node is visited, the shortest path to it has been found?
Because the algorithm always selects the unvisited node with the smallest tentative distance from the source, any alternative path to that node would be longer or equal, so the first visit finalizes the shortest path.
Related Problems
Graphs pattern
Don't just read it. Drill it.
Reconstruct Network Delay Time from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Network Delay Time drill