Solution: Network Delay Time

Let's solve the Network Delay Time problem using the Graph Algo pattern.

We'll cover the following

Statement

A network of n nodes labeled 11 to nn is provided along with a list of travel times for directed edges represented as times[i]=(xi​, yi, ti​)times[i]=(x_i​, \space y_i, \space t_i​), where xix_i​ is the source node, yiy_i​ is the target node, and tit_i​ is the delay time from the source node to the target node.

Considering we have a starting node, k, we have to determine the minimum time required for all the remaining n−1n - 1 nodes to receive the signal. Return −1-1 if it’s not possible for all n−1n - 1 nodes to receive the signal.

Constraints:

  • 1≤1 \leq k ≤\leq n ≤\leq 100100
  • 1≤1 \leq times.length ≤\leq 60006000
  • times[i].length ==3== 3
  • 1≤x,y≤1 \leq x, y \leq n
  • xx !=!= yy
  • 0≤t≤1000 \leq t \leq 100
  • Unique pairs of (x,y)(x, y), which means that there should be no multiple edges

Solution

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach is to use a simple brute force method. The algorithm would start by initializing all distances (time to travel from source to target node) to infinity, representing disconnection between the two nodes. Then, each node would use a nested loop to go through all other nodes and update their distances using the given travel times. If there is no connection between a source and a target node, its distance will not be updated. After updating all distances, the algorithm would find the maximum distance among all nodes, representing the minimum time it takes for all nodes to receive the signal. If a node that cannot be reached from node k exists, it means the distance is infinity, and it will return -1.

This approach has a time complexity of O(n2)O(n^2), where nn is the number of nodes in the graph.

Optimized approach using Dijkstra’s algorithm

Dijkstra’s algorithm is widely used for finding the shortest path between nodes in a graph. This makes it ideal for finding the minimum delay time in a network.

We will use an adjacency dictionary. The source node will be used as key, and the value is a list of tuples that have the destination node and the time for the signal to travel from source to destination node. A priority queueA priority queue is a queue where elements are assigned a priority and served according to their priority value. In our context, lower-priority elements are served before higher-priority ones. Elements with the same priority are served in the order they were added to the queue. is initialized with time initialized to 00 and starting node k as a tuple. The priority queue ensures that the node with the minimum time is retrieved in each iteration. We will iterate over the priority queue to traverse the nodes in the network. If the node is not visited, the time of the retrieved node is compared to the current delay time and updated accordingly. The neighbors of the retrieved node are found using the adjacency dictionary and are added to the queue with their times updated by adding the delay time from the retrieved node.

Finally, if all the network nodes have been visited, we will return the computed time. Otherwise, −1-1 will be returned.

The slides below illustrate how we would like the algorithm to run:

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to the Just the code section.

Step-by-step solution construction

Let’s start our solution by constructing the adjacency dictionary. The source node will be the key, whereas the destination node and the corresponding time required to travel from the source to the destinate node are going to be part of the value list. The source nodes not present in the adjacency dictionary will return an empty list.

import java.util.*;
class NetworkDelayTime {
    public static int networkDelayTime(int[][] times, int n, int k) {
        // Create adjacency dictionary
        Map<Integer, List<int[]>> adjacency = new HashMap<>();
        // Store source as key, and destination and time as values
        for (int[] time : times) {
            // Print the adjacency dictionary
            printAdjacency(adjacency);
            int source = time[0];
            int destination = time[1];
            int travelTime = time[2];
            adjacency.computeIfAbsent(source, key -> new ArrayList<>()).add(new int[]{destination, travelTime});
        }
        // Print the adjacency dictionary
        printAdjacency(adjacency);
        return -1;
    }
    // Function to print the adjacency dictionary
    private static void printAdjacency(Map<Integer, List<int[]>> adjacency) {
        System.out.print("\t Adjacency dictionary: {");
        boolean isFirst = true;
        for (Map.Entry<Integer, List<int[]>> entry : adjacency.entrySet()) {
            if (!isFirst) {
                System.out.print(", ");
            }
            int source = entry.getKey();
            List<int[]> destinations = entry.getValue();
            System.out.print(source + ": [");
            for (int i = 0; i < destinations.size(); i++) {
                int[] destination = destinations.get(i);
                System.out.print("(" + destination[0] + ", " + destination[1] + ")");
                if (i < destinations.size() - 1) {
                    System.out.print(", ");
                }
            }
            System.out.print("]");
            isFirst = false;
        }
        System.out.println("}");
    }
    public static void main(String[] args) {
        int[][][] times = {
            { {2, 1, 1}, {3, 2, 1}, {3, 4, 2} },
            { {2, 1, 1}, {1, 3, 1}, {3, 4, 2}, {5, 4, 2} },
            { {1, 2, 1}, {2, 3, 1}, {3, 4, 1} },
            { {1, 2, 1}, {2, 3, 1}, {3, 5, 2} },
            { {1, 2, 2} }
        };
        int[] n = {4, 5, 4, 5, 2};
        int[] k = {3, 1, 1, 1, 2};
        for (int i = 0; i < times.length; i++) {
            System.out.println((i + 1) + ".\t times = " + Arrays.deepToString(times[i]));
            System.out.println("\t number of nodes 'n' = " + n[i]);
            System.out.println("\t starting node 'k' = " + k[i] + "\n");
            System.out.println("\t Minimum amount of time required = " + networkDelayTime(times[i], n[i], k[i]));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Creating adjacency dictionary

In the following code, we are creating a priority queue in line 18 and adding the source node with a delay time of 00 in line 19. The priority queue stores the delay time of each node as the first element of each tuple and the node as the second element (time, node). This queue keeps track of which node needs to be processed next, with the node having the minimum delay time being processed first.

Additionally, we also initialize an empty set called visited in line 20, which will be used to track of nodes that have already been processed. The delays variable is initialized to 00 and will be used to keep track of the delay time among all the nodes in the network.

import java.util.*;
class NetworkDelayTime {
    public static int networkDelayTime(int[][] times, int n, int k) {
        // Create adjacency dictionary
        Map<Integer, List<int[]>> adjacency = new HashMap<>();
        // Store source as key, and destination and time as values
        for (int[] time : times) {
            int source = time[0];
            int destination = time[1];
            int travelTime = time[2];
            adjacency.computeIfAbsent(source, key -> new ArrayList<>()).add(new int[]{destination, travelTime});
        }
        // Print the adjacency dictionary
        printAdjacency(adjacency);
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, k});
        Set<Integer> visited = new HashSet<>();
        int delays = 0;
        System.out.println("\t pq element: " + Arrays.toString(pq.poll()));
        System.out.println("\t visited set: " + visited);
        return -1;
    }
    // Function to print the adjacency dictionary
    private static void printAdjacency(Map<Integer, List<int[]>> adjacency) {
        System.out.print("\t Adjacency dictionary: {");
        boolean isFirst = true;
        for (Map.Entry<Integer, List<int[]>> entry : adjacency.entrySet()) {
            if (!isFirst) {
                System.out.print(", ");
            }
            int source = entry.getKey();
            List<int[]> destinations = entry.getValue();
            System.out.print(source + ": [");
            for (int i = 0; i < destinations.size(); i++) {
                int[] destination = destinations.get(i);
                System.out.print("(" + destination[0] + ", " + destination[1] + ")");
                if (i < destinations.size() - 1) {
                    System.out.print(", ");
                }
            }
            System.out.print("]");
            isFirst = false;
        }
        System.out.println("}");
    }
    public static void main(String[] args) {
        int[][][] times = {
            { {2, 1, 1}, {3, 2, 1}, {3, 4, 2} },
            { {2, 1, 1}, {1, 3, 1}, {3, 4, 2}, {5, 4, 2} },
            { {1, 2, 1}, {2, 3, 1}, {3, 4, 1} },
            { {1, 2, 1}, {2, 3, 1}, {3, 5, 2} },
            { {1, 2, 2} }
        };
        int[] n = {4, 5, 4, 5, 2};
        int[] k = {3, 1, 1, 1, 2};
        for (int i = 0; i < times.length; i++) {
            System.out.println((i + 1) + ".\t times = " + Arrays.deepToString(times[i]));
            System.out.println("\t number of nodes 'n' = " + n[i]);
            System.out.println("\t starting node 'k' = " + k[i] + "\n");
            System.out.println("\t Minimum amount of time required = " + networkDelayTime(times[i], n[i], k[i]));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Creating a priority queue and a visited set

We will start a loop that continues until the pq is not empty (lines 23–49). In the loop, deqeue the tuple with the minimum delay time. Then we will check if this node has already been processed, i.e., it is present in the visited set; see line 31.

If it has not been processed, the algorithm adds the node to the visited set (line 34) and updates the delays value (line 35) if the node’s delay time is greater than the current delays value.

Next, the neighbors of the current node are retrieved from the adjacency dictionary (line 36), and for each unvisited neighbor, its delay time (line 45) is computed by adding the delay time of the current node and the delay time between the current node and the neighbor. These neighbors are then added to the pq (line 46) so they can be processed in the next iteration of the while loop.

import java.util.*;
class NetworkDelayTime {
    public static int networkDelayTime(int[][] times, int n, int k) {
        // Create adjacency dictionary
        Map<Integer, List<int[]>> adjacency = new HashMap<>();
        // Store source as key, and destination and time as values
        for (int[] time : times) {
            int source = time[0];
            int destination = time[1];
            int travelTime = time[2];
            adjacency.computeIfAbsent(source, key -> new ArrayList<>()).add(new int[]{destination, travelTime});
        }
        // Print the adjacency dictionary
        printAdjacency(adjacency);
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, k});
        Set<Integer> visited = new HashSet<>();
        int delays = 0;
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int time = current[0];
            int node = current[1];
            System.out.println("\t Retrieved time: " + time);
            System.out.println("\t Retrieved node: " + node);
            if (visited.contains(node))
                continue;
            visited.add(node);
            delays = Math.max(delays, time);
            List<int[]> neighbors = adjacency.getOrDefault(node, new ArrayList<>());
            // Print the neighbors
            printNeighbors(neighbors);
            for (int[] neighbor : neighbors) {
                int neighborNode = neighbor[0];
                int neighborTime = neighbor[1];
                if (!visited.contains(neighborNode)) {
                    int newTime = time + neighborTime;
                    pq.offer(new int[]{newTime, neighborNode});
                }
            }
        }
        return -1;
    }
    // Function to print the adjacency dictionary
    private static void printAdjacency(Map<Integer, List<int[]>> adjacency) {
        System.out.print("\t Adjacency dictionary: {");
        boolean isFirst = true;
        for (Map.Entry<Integer, List<int[]>> entry : adjacency.entrySet()) {
            if (!isFirst) {
                System.out.print(", ");
            }
            int source = entry.getKey();
            List<int[]> destinations = entry.getValue();
            System.out.print(source + ": [");
            for (int i = 0; i < destinations.size(); i++) {
                int[] destination = destinations.get(i);
                System.out.print("(" + destination[0] + ", " + destination[1] + ")");
                if (i < destinations.size() - 1) {
                    System.out.print(", ");
                }
            }
            System.out.print("]");
            isFirst = false;
        }
        System.out.println("}");
    }
    // Function to print the neighbors
    private static void printNeighbors(List<int[]> neighbors) {
        System.out.print("\t Neighbors: [");
        for (int i = 0; i < neighbors.size(); i++) {
            int[] neighbor = neighbors.get(i);
            System.out.print("(" + neighbor[0] + ", " + neighbor[1] + ")");
            if (i < neighbors.size() - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }   
    public static void main(String[] args) {
        int[][][] times = {
            { {2, 1, 1}, {3, 2, 1}, {3, 4, 2} },
            { {2, 1, 1}, {1, 3, 1}, {3, 4, 2}, {5, 4, 2} },
            { {1, 2, 1}, {2, 3, 1}, {3, 4, 1} },
            { {1, 2, 1}, {2, 3, 1}, {3, 5, 2} },
            { {1, 2, 2} }
        };
        int[] n = {4, 5, 4, 5, 2};
        int[] k = {3, 1, 1, 1, 2};
        for (int i = 0; i < times.length; i++) {
            System.out.println((i + 1) + ".\t times = " + Arrays.deepToString(times[i]));
            System.out.println("\t number of nodes 'n' = " + n[i]);
            System.out.println("\t starting node 'k' = " + k[i] + "\n");
            System.out.println("\t Minimum amount of time required = " + networkDelayTime(times[i], n[i], k[i]));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Iterating through priority queue

Finally, we will check if the number of nodes visited equals the total number of nodes, n (line 51). If TRUE, we will return the delay time stored in the delays (line 52); otherwise, return −1-1. This step ensures that the algorithm has processed all the nodes. If all nodes have not been processed, it indicates that some nodes in the network are not reachable from the source node.

import java.util.*;
class NetworkDelayTime {
    public static int networkDelayTime(int[][] times, int n, int k) {
        // Create adjacency dictionary
        Map<Integer, List<int[]>> adjacency = new HashMap<>();
        // Store source as key, and destination and time as values
        for (int[] time : times) {
            int source = time[0];
            int destination = time[1];
            int travelTime = time[2];
            adjacency.computeIfAbsent(source, key -> new ArrayList<>()).add(new int[]{destination, travelTime});
        }
        // Print the adjacency dictionary
        printAdjacency(adjacency);
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, k});
        Set<Integer> visited = new HashSet<>();
        int delays = 0;
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int time = current[0];
            int node = current[1];
            System.out.println("\t Retrieved time: " + time);
            System.out.println("\t Retrieved node: " + node);
            if (visited.contains(node))
                continue;
            visited.add(node);
            delays = Math.max(delays, time);
            List<int[]> neighbors = adjacency.getOrDefault(node, new ArrayList<>());
            // Print the neighbors
            printNeighbors(neighbors);
            for (int[] neighbor : neighbors) {
                int neighborNode = neighbor[0];
                int neighborTime = neighbor[1];
                if (!visited.contains(neighborNode)) {
                    int newTime = time + neighborTime;
                    pq.offer(new int[]{newTime, neighborNode});
                }
            }
        }
        if (visited.size() == n)
            return delays;
        return -1;
    }
    // Function to print the adjacency dictionary
    private static void printAdjacency(Map<Integer, List<int[]>> adjacency) {
        System.out.print("\t Adjacency dictionary: {");
        boolean isFirst = true;
        for (Map.Entry<Integer, List<int[]>> entry : adjacency.entrySet()) {
            if (!isFirst) {
                System.out.print(", ");
            }
            int source = entry.getKey();
            List<int[]> destinations = entry.getValue();
            System.out.print(source + ": [");
            for (int i = 0; i < destinations.size(); i++) {
                int[] destination = destinations.get(i);
                System.out.print("(" + destination[0] + ", " + destination[1] + ")");
                if (i < destinations.size() - 1) {
                    System.out.print(", ");
                }
            }
            System.out.print("]");
            isFirst = false;
        }
        System.out.println("}");
    }
    // Function to print the neighbors
    private static void printNeighbors(List<int[]> neighbors) {
        System.out.print("\t Neighbors: [");
        for (int i = 0; i < neighbors.size(); i++) {
            int[] neighbor = neighbors.get(i);
            System.out.print("(" + neighbor[0] + ", " + neighbor[1] + ")");
            if (i < neighbors.size() - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }   
    public static void main(String[] args) {
        int[][][] times = {
            { {2, 1, 1}, {3, 2, 1}, {3, 4, 2} },
            { {2, 1, 1}, {1, 3, 1}, {3, 4, 2}, {5, 4, 2} },
            { {1, 2, 1}, {2, 3, 1}, {3, 4, 1} },
            { {1, 2, 1}, {2, 3, 1}, {3, 5, 2} },
            { {1, 2, 2} }
        };
        int[] n = {4, 5, 4, 5, 2};
        int[] k = {3, 1, 1, 1, 2};
        for (int i = 0; i < times.length; i++) {
            System.out.println((i + 1) + ".\t times = " + Arrays.deepToString(times[i]));
            System.out.println("\t number of nodes 'n' = " + n[i]);
            System.out.println("\t starting node 'k' = " + k[i] + "\n");
            System.out.println("\t Minimum amount of time required = " + networkDelayTime(times[i], n[i], k[i]));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Checking if all nodes visited or not

Just the code

Here’s the complete solution to this problem:

import java.util.*;
class NetworkDelayTime {
    public static int networkDelayTime(int[][] times, int n, int k) {
        Map<Integer, List<int[]>> adjacency = new HashMap<>();
        for (int[] time : times) {
            int source = time[0];
            int destination = time[1];
            int travelTime = time[2];
            adjacency.computeIfAbsent(source, key -> new ArrayList<>()).add(new int[]{destination, travelTime});
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, k});
        Set<Integer> visited = new HashSet<>();
        int delays = 0;
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int time = current[0];
            int node = current[1];
            if (visited.contains(node))
                continue;
            visited.add(node);
            delays = Math.max(delays, time);
            List<int[]> neighbors = adjacency.getOrDefault(node, new ArrayList<>());
            for (int[] neighbor : neighbors) {
                int neighborNode = neighbor[0];
                int neighborTime = neighbor[1];
                if (!visited.contains(neighborNode)) {
                    int newTime = time + neighborTime;
                    pq.offer(new int[]{newTime, neighborNode});
                }
            }
        }
        if (visited.size() == n)
            return delays;
        return -1;
    }
    public static void main(String[] args) {
        int[][][] times = {
            { {2, 1, 1}, {3, 2, 1}, {3, 4, 2} },
            { {2, 1, 1}, {1, 3, 1}, {3, 4, 2}, {5, 4, 2} },
            { {1, 2, 1}, {2, 3, 1}, {3, 4, 1} },
            { {1, 2, 1}, {2, 3, 1}, {3, 5, 2} },
            { {1, 2, 2} }
        };
        int[] n = {4, 5, 4, 5, 2};
        int[] k = {3, 1, 1, 1, 2};
        for (int i = 0; i < times.length; i++) {
            System.out.println((i + 1) + ".\t times = " + Arrays.deepToString(times[i]));
            System.out.println("\t number of nodes 'n' = " + n[i]);
            System.out.println("\t starting node 'k' = " + k[i] + "\n");
            System.out.println("\t Minimum amount of time required = " + networkDelayTime(times[i], n[i], k[i]));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Network Delay Time

Solution summary

The algorithm can be summarized in the following steps:

  1. Create an adjacency dictionary to store the information of the nodes and their edges.

  2. Use a priority queue to store the nodes and their delay times. Initialize the queue with the source node and a delay time of 0.

  3. Use a visited set to track the nodes that have already been processed.

  4. Process the nodes from the priority queue by first visiting the node with the smallest delay time and updating the delay time if necessary.

  5. Add the unvisited neighbors of the processed node to the priority queue with their new delay times.

  6. Return the delay time if all nodes have been processed. Otherwise, return −1-1.

Time complexity

This algorithm takes O(Elog⁡N)O(E\log N), where EE is the total number of edges, and NN is the number of nodes in the network since push and pop operations on the priority queue take O(log⁡N)O(\log N) time.

Space complexity

The space complexity is O(N+E)O(N+E), where NN is the number of nodes in the graph, and EE is the number of edges required by the adjacency dictionary and priority queue.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.