743. Network Delay Time

Published on May 3, 2023

Question

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.

Algorithm

This question is a typical shortest path problem. I use Dijkstra algorithm to solve it. We do bfs and maintain a minDistTo, finally we check the max value, if it could not send to all the nodes, the res would be MAX_VALUE, otherwise, the max value is the min value or latency required to send signal to all the nodes.

Code2 is the standard answer, which optimize the time by maintain an adjacency list.

Code

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        int[] minDistTo = new int[n + 1];
        boolean[] visited = new boolean[n + 1];
        Arrays.fill(minDistTo, Integer.MAX_VALUE);
        PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>((a, b) -> (a.getValue() - b.getValue()));
        
        minDistTo[k] = 0;
        pq.offer(new Pair(k, minDistTo[1]));
        
        while (!pq.isEmpty()) {
            Pair<Integer, Integer> pair = pq.poll();
            visited[pair.getKey()] = true;
            int curNode = pair.getKey();
            for (int[] time : times) {
                int start = time[0];
                int end = time[1];
                int latency = time[2];
                if (start == curNode && !visited[end]) {
                    int curDist = minDistTo[start] + latency;
                    if (curDist < minDistTo[end]) {
                        minDistTo[end] = curDist;
                        pq.offer(new Pair(end, curDist));
                    }
                }
            }
        }
        
        int res = Integer.MIN_VALUE;
        for (int i = 1; i < minDistTo.length; i++) {
            res = Math.max(minDistTo[i], res);
        }
        return res != Integer.MAX_VALUE ? res : -1;
        
    }
}

Code2

class Solution {
    // Adjacency list
    Map<Integer, List<Pair<Integer, Integer>>> adj = new HashMap<>();
    
    private void dijkstra(int[] signalReceivedAt, int source, int n) {
        Queue<Pair<Integer, Integer>> pq = new PriorityQueue<Pair<Integer,Integer>>
            (Comparator.comparing(Pair::getKey));
        pq.add(new Pair(0, source));
        
        // Time for starting node is 0
        signalReceivedAt[source] = 0;
        
        while (!pq.isEmpty()) {
            Pair<Integer, Integer> topPair = pq.remove();
            
            int currNode = topPair.getValue();
            int currNodeTime = topPair.getKey();
            
            if (currNodeTime > signalReceivedAt[currNode]) {
                continue;
            }
            
            if (!adj.containsKey(currNode)) {
                continue;
            }
            
            // Broadcast the signal to adjacent nodes
            for (Pair<Integer, Integer> edge : adj.get(currNode)) {
                int time = edge.getKey();
                int neighborNode = edge.getValue();
                
                // Fastest signal time for neighborNode so far
                // signalReceivedAt[currNode] + time : 
                // time when signal reaches neighborNode
                if (signalReceivedAt[neighborNode] > currNodeTime + time) {
                    signalReceivedAt[neighborNode] = currNodeTime + time;
                    pq.add(new Pair(signalReceivedAt[neighborNode], neighborNode));
                }
            }
        }
    }
    
    public int networkDelayTime(int[][] times, int n, int k) {
        // Build the adjacency list
        for (int[] time : times) {
            int source = time[0];
            int dest = time[1];
            int travelTime = time[2];
            
            adj.putIfAbsent(source, new ArrayList<>());
            adj.get(source).add(new Pair(travelTime, dest));
        }
        
        int[] signalReceivedAt = new int[n + 1];
        Arrays.fill(signalReceivedAt, Integer.MAX_VALUE);
        
        dijkstra(signalReceivedAt, k, n);
        
        int answer = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            answer = Math.max(answer, signalReceivedAt[i]);
        }
        
        // INT_MAX signifies atleat one node is unreachable
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
}