Vultr DocsLatest Content

Network Delay Time

Updated on 18 June, 2025
Network Delay Time header image

Problem Statement

In this problem, you are provided with a representation of a network consisting of n nodes, each identified by a unique label ranging from 1 to n. These nodes are connected through a set of directed edges where each edge has an associated travel time. The edges are given in the list times, where each element times[i] is a trio (ui, vi, wi). Here, ui represents the source node from which the signal starts, vi is the destination node where the signal is directed, and wi is the time taken for the signal to travel from the source node ui to the destination node vi.

The main task is to determine the minimum time required for a signal emitted from a specified starting node k to reach all other nodes in the network. The result should be the least amount of time after which every node has received the signal from node k. If at least one node is unreachable from the source node k, the function should return -1, indicating that not all nodes can receive the signal.

Examples

Example 1

Input:

times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2

Output:

2

Example 2

Input:

times = [[1,2,1]], n = 2, k = 1

Output:

1

Example 3

Input:

times = [[1,2,1]], n = 2, k = 2

Output:

-1

Constraints

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • times[i].length == 3
  • 1 <= ui, vi <= n
  • ui != vi
  • 0 <= wi <= 100
  • All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

Approach and Intuition

To solve this problem, we need to determine the shortest path from the starting node k to all other nodes and compute the longest of these shortest paths as it represents the bottlenecks in signal transmission. Here's the step-by-step intuition and approach for the solution:

  1. Recognize that the problem asks for the shortest paths from a single source to all other nodes and also the maximum among those shortest paths. This is a classical Single Source Shortest Path (SSSP) problem on a weighted, directed graph.

  2. Given the nature of the input where we have to find paths to multiple nodes, Dijkstra's Algorithm is a suitable choice. Dijkstra's algorithm efficiently finds the shortest path from a single source to all other nodes in a graph with non-negative edge weights.

  3. Initialization: Start by initializing a distance array where each element represents the minimum time taken for the signal to reach node i from node k. Initialize it with a large value (like infinity) for all nodes except the start node k, which is initialized to zero since it takes no time for the signal to start at k.

  4. Using a Priority Queue: Utilize a priority queue to continually process the node with the current shortest known path from k. Extract the node u with the smallest distance and update its neighbors' distances.

  5. Relaxation: For each neighbor v of u, if the path to v through u offers a shorter path than previously known, update the shortest path to v.

  6. Termination: Once the priority queue is empty, all reachable nodes would have the shortest path from k. If the largest value in the distance array is still infinity, return -1 as not all nodes are reachable. Otherwise, return the maximum value from the distance array.

By following these steps, we use a combination of Dijkstra's algorithm and some minor additional processing to find out the required maximum time for all nodes to receive the signal or determine if some nodes are unreachable.

Solutions

  • C++
  • Java
cpp 
class NetworkDelay {
public:
    vector<pair<int, int>> graph[101];

    void shortestPath(vector<int>& signalsAtTime, int start, int nodeCount) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
        minHeap.push({0, start});
        
        signalsAtTime[start] = 0;
        
        while (!minHeap.empty()) {
            int currentMinTime = minHeap.top().first;
            int currentNode = minHeap.top().second;
            minHeap.pop();
            
            if (currentMinTime > signalsAtTime[currentNode]) continue;
            
            for (pair<int, int> connection : graph[currentNode]) {
                int timeToNext = connection.first;
                int nextNode = connection.second;
                
                if (signalsAtTime[nextNode] > currentMinTime + timeToNext) {
                    signalsAtTime[nextNode] = currentMinTime + timeToNext;
                    minHeap.push({signalsAtTime[nextNode], nextNode});
                }
            }
        }
    }
    
    int calculateNetworkDelay(vector<vector<int>>& timeDelays, int nodeCount, int startNode) {
        for (vector<int> timeDelay : timeDelays) {
            int src = timeDelay[0];
            int dest = timeDelay[1];
            int dur = timeDelay[2];
            
            graph[src].push_back({dur, dest});
        }
        
        vector<int> signalsAtTime(nodeCount + 1, INT_MAX);
        shortestPath(signalsAtTime, startNode, nodeCount);
        
        int maxDelay = INT_MIN;
        for (int i = 1; i <= nodeCount; i++) {
            maxDelay = max(maxDelay, signalsAtTime[i]);
        }
        
        return maxDelay == INT_MAX ? -1 : maxDelay;
    }
};

This code implements the solution for the Network Delay Time problem using C++ where the task is to calculate the time it takes for a signal to reach all nodes in a network. The nodes and their connections are represented as a directed graph, and the signal transmission delay between nodes is provided as input.

Key components of the code:

  • graph[101]: Represents the network with a maximum of 100 nodes as an array of vectors, each holding pairs consisting of transmission time and the destination node.

  • shortestPath Function:

    • Utilizes Dijkstra’s algorithm with a priority queue to find the shortest path from the starting node to all other nodes.
    • Accepts a reference to a vector signalsAtTime to store the shortest time required to reach each node from the start node.
    • Starts by pushing the start node with a delay of 0 into the queue, then processes each node, updating the times for its neighbouring nodes.

  • calculateNetworkDelay Function:

    • Builds the graph using the input vector timeDelays, where each element contains the source node, destination node, and delay.
    • Initializes the signalsAtTime vector to store the maximum possible values (INT_MAX), representing an initial state where no nodes are reachable.
    • Invokes shortestPath to compute the minimum delay times from the start node to all other nodes.
    • Determines the maximum delay among all nodes, thus finding the longest time required for a signal to reach a node from the start node.
    • Returns the maximum delay or -1 if not all nodes are reachable.

To utilize this class:

  1. Create an instance of NetworkDelay.
  2. Use the calculateNetworkDelay method by passing the required parameters: a list of time delays (each as a vector of three integers), total node count, and the starting node number.

The result will be either the overall maximum delay time if the signal can reach all nodes or -1 if any node remains unreachable from the start node. This solution is efficient for networks with up to 100 nodes but can be adjusted for larger networks by increasing the size of the graph array.

java 
class NetworkDelay {
    // Maintain a map for adjacency relationships
    Map<Integer, List<Pair<Integer, Integer>>> adjacency = new HashMap<>();

    private void executeDijkstra(int[] delays, int start, int vertices) {
        PriorityQueue<Pair<Integer, Integer>> minHeap = new PriorityQueue<>(Comparator.comparing(Pair::getKey));
        minHeap.add(new Pair(0, start));
        
        // Initialize the start vertex delay to zero
        delays[start] = 0;
        
        while (!minHeap.isEmpty()) {
            Pair<Integer, Integer> currentPair = minHeap.poll();
            
            int currentNode = currentPair.getValue();
            int currentTime = currentPair.getKey();
            
            if (currentTime > delays[currentNode]) {
                continue;
            }

            if (!adjacency.containsKey(currentNode)) {
                continue;
            }
            
            // Explore edges to neighbors
            for (Pair<Integer, Integer> edge : adjacency.get(currentNode)) {
                int edgeTime = edge.getKey();
                int neighbor = edge.getValue();
                
                if (delays[neighbor] > currentTime + edgeTime) {
                    delays[neighbor] = currentTime + edgeTime;
                    minHeap.add(new Pair(delays[neighbor], neighbor));
                }
            }
        }
    }
    
    public int calculateNetworkDelayTime(int[][] times, int n, int k) {
        // Construct the adjacency list from times data
        for (int[] time : times) {
            int u = time[0];
            int v = time[1];
            int t = time[2];
            
            if (!adjacency.containsKey(u)) {
                adjacency.put(u, new ArrayList<>());
            }
            adjacency.get(u).add(new Pair(t, v));
        }
        
        int[] delays = new int[n + 1];
        Arrays.fill(delays, Integer.MAX_VALUE);
        
        executeDijkstra(delays, k, n);
        
        int maxDelay = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            maxDelay = Math.max(maxDelay, delays[i]);
        }
        
        return maxDelay == Integer.MAX_VALUE ? -1 : maxDelay;
    }
}

This Java implementation tackles the problem of determining the network delay time in a directed graph using Dijkstra's algorithm. The approach involves calculating the shortest time it takes for a signal to travel from a starting node to all other nodes in the network.

  • Begin by setting up an adjacency list to model the network using a HashMap where each node points to a list of pairs. Each pair contains the neighbor node and the time delay to that node.

  • Implement the executeDijkstra method which utilizes a priority queue to process nodes based on their current known shortest delay time. For each node processed, update the potential shorter delay times for its neighboring nodes.

  • In the calculateNetworkDelayTime function, initialize the adjacency list using the input time data for each edge (node pair and delay). Start off each node's delay with infinity (except for the starting node).

  • Post processing, iterate over all node delays to find the maximum time among them. If the maximum delay remains Integer.MAX_VALUE, return -1 indicating some nodes are unreachable; otherwise, return the maximum delay.

This solution effectively computes the required delay time for signals to propagate through the entire network, giving insights into network performance constraints and efficiencies.

Comments

No comments yet.