890078. Network Delay Time
Network Delay Time
Slug: network-delay-time
Difficulty: Medium
Id: 890078
Summary
The Network Delay Time problem involves finding the minimum time it takes to send packets from a source node to all other nodes in a network. The network is represented as a graph, where each edge has a weight representing the delay for sending a packet over that edge. The goal is to find the minimum total delay required to send packets from the source node to all other nodes.
Detailed Explanation
The problem can be solved by using Dijkstra's algorithm with a slight modification. We need to find the shortest path from the source node to each of the other nodes, considering the delay for sending packets over each edge. The key concept involved is dynamic programming.
Here's a step-by-step breakdown of the solution:
- Initialize a distance array
dwith infinite values for all nodes except the source node, which is set to 0. - Create a priority queue
pqand enqueue the source node with a delay of 0. - While the priority queue is not empty:
- Dequeue the node with the minimum delay from the priority queue.
- For each neighbor node of the dequeued node that has not been visited yet:
- Calculate the total delay to reach the neighbor node by adding the delay of the edge between the two nodes and the delay of the dequeued node.
- If this calculated delay is less than the current value in the distance array, update the distance array with the new delay.
- The minimum delay required to send packets from the source node to all other nodes is the maximum value in the distance array.
Time complexity: O(E log E), where E is the number of edges in the graph. Space complexity: O(V), where V is the number of vertices (nodes) in the graph.
Optimized Solutions
Java
import java.util.*;
class Solution {
public int networkDelayTime(int[][] times, int N, int K) {
List<List<int[]>> graph = new ArrayList<>();
for (int i = 0; i < N; i++) {
graph.add(new ArrayList<>());
}
for (int[] time : times) {
graph.get(time[1] - 1).add(new int[]{time[0] - 1, time[2]});
}
int[] dist = new int[N];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[K - 1] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
pq.offer(new int[]{K - 1, 0});
while (!pq.isEmpty()) {
int[] node = pq.poll();
for (int[] edge : graph.get(node[0])) {
if (dist[edge[0]] > dist[node[0]] + edge[1]) {
dist[edge[0]] = dist[node[0]] + edge[1];
pq.offer(new int[]{edge[0], dist[edge[0]]});
}
}
}
int maxDelay = 0;
for (int d : dist) {
if (d == Integer.MAX_VALUE) return -1;
maxDelay = Math.max(maxDelay, d);
}
return maxDelay;
}
}