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 d with infinite values for all nodes except the source node, which is set to 0.
Create a priority queue pq and 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

View GeeksforGeeks Problem

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;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Sign in to devexcode.com with google.com

890078. Network Delay Time