Network Delay Time
MedPrompt
You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.
We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.
Example 1:
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2Example 2:
Input: times = [[1,2,1]], n = 2, k = 1
Output: 1Example 3:
Input: times = [[1,2,1]], n = 2, k = 2
Output: -1
Constraints:
1 <= k <= n <= 1001 <= times.length <= 6000times[i].length == 31 <= ui, vi <= nui != vi0 <= wi <= 100- All the pairs
(ui, vi)are unique. (i.e., no multiple edges.)
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses the Bellman-Ford algorithm to find the shortest paths from the source node k to all other nodes. Bellman-Ford is capable of handling graphs with negative edge weights, although this problem has only non-negative weights. It works by iteratively relaxing edges, which involves repeatedly checking and updating shortest path estimates until they converge.
Algorithm
- Initialize a distance array
distof sizen+1with a large value (infinity) to store the shortest travel times fromk. - Set
dist[k] = 0. - Repeat
n-1times:- For each edge
(u, v)with weightwintimes:- If
dist[u]is not infinity anddist[u] + w < dist[v], updatedist[v] = dist[u] + w.
- If
- For each edge
- After the loops, find the maximum value in the
distarray (fromdist[1]todist[n]). Let this bemax_dist. - If
max_distis infinity, it means at least one node is unreachable. Return -1. - Otherwise, return
max_dist.
Walkthrough
The Bellman-Ford algorithm computes single-source shortest paths in a weighted directed graph. First, we initialize a distance array dist of size n+1 with infinity for all nodes, except for the source node k, which is set to 0. The algorithm then relaxes all edges (u, v) with weight w for n-1 times. A relaxation step checks if the path to v can be shortened by going through u. If dist[u] + w < dist[v], we update dist[v] to dist[u] + w. After n-1 iterations, the dist array will contain the shortest path distances from k to all other nodes, provided there are no negative-weight cycles (which is true here). Finally, we find the maximum distance in the dist array among all reachable nodes. If any distance is still infinity, it means that node is unreachable, and we should return -1. The result is the maximum finite distance found.
import java.util.Arrays; class Solution { public int networkDelayTime(int[][] times, int n, int k) { int[] dist = new int[n + 1]; Arrays.fill(dist, Integer.MAX_VALUE); dist[k] = 0; for (int i = 0; i < n - 1; i++) { boolean updated = false; for (int[] edge : times) { int u = edge[0]; int v = edge[1]; int w = edge[2]; if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) { dist[v] = dist[u] + w; updated = true; } } // Optimization: if no distances were updated in an iteration, we can stop early. if (!updated) { break; } } int maxWait = 0; for (int i = 1; i <= n; i++) { if (dist[i] == Integer.MAX_VALUE) { return -1; } maxWait = Math.max(maxWait, dist[i]); } return maxWait; }}Complexity
Time
O(n * E), where `n` is the number of nodes and `E` is the number of edges. The outer loop runs `n-1` times, and the inner loop iterates through all `E` edges.
Space
O(n) to store the `dist` array.
Trade-offs
Pros
Relatively simple to implement.
Can handle negative edge weights (though not needed for this problem).
Cons
Less efficient than Dijkstra's algorithm for graphs with non-negative weights.
For the given constraints, it's the slowest approach.
This is the standard and widely-used implementation of Dijkstra's algorithm. It finds the shortest paths from a source node to all other nodes in a weighted graph with non-negative edge weights. It uses a priority queue (min-heap) to efficiently select the next node to visit based on the current shortest known distance.
Algorithm
- Build an adjacency list
adjwhereadj[u]contains pairs of(v, w)for each neighborvofuwith edge weightw. - Initialize a distance array
distof sizen+1with infinity, and setdist[k] = 0. - Create a priority queue
pqand add the starting nodekwith distance 0, i.e.,pq.add({0, k}). - While
pqis not empty:- Extract the node
uwith the minimum distance frompq. - If the extracted distance is greater than
dist[u], continue (this is an outdated entry). - For each neighbor
vofuwith edge weightw:- If
dist[u] + w < dist[v]:- Update
dist[v] = dist[u] + w. - Add
{dist[v], v}topq.
- Update
- If
- Extract the node
- After the loop, find the maximum value in
dist(fromdist[1]todist[n]). - If the maximum value is infinity, return -1.
- Otherwise, return the maximum value.
Walkthrough
The algorithm maintains a set of visited nodes and a priority queue of nodes to visit. The priority queue stores pairs of (distance, node) and is ordered by distance. First, we build an adjacency list representation of the graph. We initialize a dist array with infinity for all nodes and 0 for the source node k. We add (0, k) to the priority queue. While the priority queue is not empty, we extract the node u with the smallest distance. If u has already been processed with a shorter or equal path, we skip it. Otherwise, for each neighbor v of u, we calculate the new potential distance through u. If dist[u] + weight(u, v) < dist[v], we update dist[v] and add the new pair (dist[v], v) to the priority queue. The algorithm terminates when the priority queue is empty. Finally, we find the maximum distance in the dist array. If any node is unreachable (distance is infinity), we return -1. Otherwise, we return the maximum distance.
import java.util.*; class Solution { public int networkDelayTime(int[][] times, int n, int k) { Map<Integer, List<int[]>> adj = new HashMap<>(); for (int[] time : times) { adj.computeIfAbsent(time[0], key -> new ArrayList<>()).add(new int[]{time[1], time[2]}); } int[] dist = new int[n + 1]; Arrays.fill(dist, Integer.MAX_VALUE); dist[k] = 0; PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); pq.offer(new int[]{0, k}); // {distance, node} while (!pq.isEmpty()) { int[] current = pq.poll(); int d = current[0]; int u = current[1]; if (d > dist[u]) { continue; } if (adj.containsKey(u)) { for (int[] edge : adj.get(u)) { int v = edge[0]; int w = edge[1]; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.offer(new int[]{dist[v], v}); } } } } int maxWait = 0; for (int i = 1; i <= n; i++) { if (dist[i] == Integer.MAX_VALUE) { return -1; } maxWait = Math.max(maxWait, dist[i]); } return maxWait; }}Complexity
Time
O(E log n), where `E` is the number of edges and `n` is the number of nodes. Each vertex is added to the priority queue once. Each edge relaxation might add an element to the priority queue, leading to at most `E` insertions. Both poll and offer operations on the priority queue take O(log n) time.
Space
O(n + E) for the adjacency list, the distance array, and the priority queue. In the worst case, the priority queue can hold `E` elements.
Trade-offs
Pros
Generally very efficient for sparse graphs.
A standard and well-understood algorithm for shortest paths.
Cons
Slightly more complex to implement than the simple array-based version.
For dense graphs, where
Eis close ton^2, its performance can be worse than the O(n^2) implementation. For this problem's specific constraints, it's slightly slower than the array-based version.
This approach implements Dijkstra's algorithm without an optimized priority queue. Instead of a min-heap, it uses a simple array and a linear scan to find the unvisited node with the minimum distance in each iteration. This is surprisingly effective for dense graphs or graphs with a small number of vertices, as is the case with this problem's constraints.
Algorithm
- Build an adjacency list
adjfor the graph. - Initialize a distance array
distof sizen+1with infinity, and setdist[k] = 0. - Initialize a boolean array
visitedof sizen+1tofalse. - Repeat
ntimes:- Find the unvisited node
uwith the minimumdistvalue by scanning all nodes. If no such node can be found (all remaining nodes have infinite distance), break the loop. - Mark
uas visited:visited[u] = true. - For each neighbor
vofuwith edge weightw:- If
!visited[v]anddist[u] + w < dist[v]:- Update
dist[v] = dist[u] + w.
- Update
- If
- Find the unvisited node
- After the loop, find the maximum value in
dist(fromdist[1]todist[n]). - If the maximum value is infinity, return -1.
- Otherwise, return the maximum value.
Walkthrough
This version of Dijkstra's algorithm is conceptually similar to the priority queue version but differs in how it selects the next node to process. We start by building an adjacency list for the graph. We maintain a dist array, initialized to infinity for all nodes except the source k (which is 0), and a boolean array visited to keep track of processed nodes. The main loop runs n times. In each iteration, we scan through all n nodes to find the unvisited node u with the smallest distance in the dist array. Once u is found, we mark it as visited. Then, we relax all the edges starting from u. For each neighbor v of u, if we can find a shorter path to v via u, we update dist[v]. After the main loop finishes, the dist array contains the shortest path distances. The final result is the maximum distance in the dist array, or -1 if any node is unreachable.
import java.util.*; class Solution { public int networkDelayTime(int[][] times, int n, int k) { List<List<int[]>> adj = new ArrayList<>(); for (int i = 0; i <= n; i++) { adj.add(new ArrayList<>()); } for (int[] time : times) { adj.get(time[0]).add(new int[]{time[1], time[2]}); } int[] dist = new int[n + 1]; Arrays.fill(dist, Integer.MAX_VALUE); boolean[] visited = new boolean[n + 1]; dist[k] = 0; for (int i = 0; i < n; i++) { int u = -1; int min_dist = Integer.MAX_VALUE; // Find the unvisited node with the smallest distance for (int j = 1; j <= n; j++) { if (!visited[j] && dist[j] < min_dist) { min_dist = dist[j]; u = j; } } // If no reachable unvisited node is found if (u == -1) break; visited[u] = true; // Relax edges for (int[] edge : adj.get(u)) { int v = edge[0]; int w = edge[1]; if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) { dist[v] = dist[u] + w; } } } int maxWait = 0; for (int i = 1; i <= n; i++) { if (dist[i] == Integer.MAX_VALUE) { return -1; } maxWait = Math.max(maxWait, dist[i]); } return maxWait; }}Complexity
Time
O(n^2 + E). The outer loop runs `n` times. Inside, finding the minimum distance node takes O(n) time. This gives O(n^2). The edge relaxations happen over the course of the algorithm for all `E` edges in total. So the total complexity is dominated by O(n^2).
Space
O(n + E) for the adjacency list, distance array, and visited array.
Trade-offs
Pros
Very efficient for dense graphs where
Eis close ton^2.For the given problem constraints (n <= 100), this O(n^2) approach is the most efficient.
Implementation is straightforward without requiring a Priority Queue data structure.
Cons
Inefficient for sparse graphs where
Eis much smaller thann^2.
Solutions
Solution
class Solution {private static final int N = 110;private static final int INF = 0x3f3f;public int networkDelayTime(int[][] times, int n, int k) { int[][] g = new int[N][N]; for (int i = 0; i < N; ++i) { Arrays.fill(g[i], INF); } for (int[] e : times) { g[e[0]][e[1]] = e[2]; } int[] dist = new int[N]; Arrays.fill(dist, INF); dist[k] = 0; boolean[] vis = new boolean[N]; for (int i = 0; i < n; ++i) { int t = -1; for (int j = 1; j <= n; ++j) { if (!vis[j] && (t == -1 || dist[t] > dist[j])) { t = j; } } vis[t] = true; for (int j = 1; j <= n; ++j) { dist[j] = Math.min(dist[j], dist[t] + g[t][j]); } } int ans = 0; for (int i = 1; i <= n; ++i) { ans = Math.max(ans, dist[i]); } return ans == INF ? -1 : ans; }}class Solution {public: const int inf = 0x3f3f; int networkDelayTime(vector<vector<int>> ×, int n, int k) { vector<vector<int>> g(n, vector<int>(n, inf)); for (auto &t : times) g[t[0] - 1][t[1] - 1] = t[2]; vector<bool> vis(n); vector<int> dist(n, inf); dist[k - 1] = 0; for (int i = 0; i < n; ++i) { int t = -1; for (int j = 0; j < n; ++j) { if (!vis[j] && (t == -1 || dist[t] > dist[j])) { t = j; } } vis[t] = true; for (int j = 0; j < n; ++j) { dist[j] = min(dist[j], dist[t] + g[t][j]); } } int ans = *max_element(dist.begin(), dist.end()); return ans == inf ? -1 : ans; }};class Solution: def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int: INF = 0x3F3F g = defaultdict(list) for u, v, w in times: g[u - 1]. append((v - 1, w)) dist = [INF] * n dist[k - 1] = 0 q = [(0, k - 1)] while q: _, u = heappop(q) for v, w in g[u]: if dist[v] > dist[u] + w: dist[v] = dist[u] + w heappush(q, (dist[v], v)) ans = max(dist) return - 1 if ans == INF else ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.