743. Network Delay Time

Description

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Note:

1. N will be in the range [1, 100].
2. K will be in the range [1, N].
3. The length of times will be in the range [1, 6000].
4. All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 1 <= w <= 100.

Solution

Djikstra

It is a direct graph.

• Use Map<Integer, Map<Integer, Integer>> to store the source node, target node and the distance between them.
• Offer the node K to a PriorityQueue.
• Then keep getting the closest nodes to the current node and calculate the distance from the source (K) to this node (absolute distance). Use a Map to store the shortest absolute distance of each node.
• Return the node with the largest absolute distance.

class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        // build a directed graph
        Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
        for (int i = 1; i <= N; ++i) {
            graph.put(i, new HashMap<>());
        }
        
        for (int[] time : times) {
            graph.get(time[0]).put(time[1], time[2]);
        }
        
        Map<Integer, Integer> timeMap = new HashMap<>();
        PriorityQueue<Map.Entry<Integer, Integer>> queue 
            = new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
        queue.addAll(graph.get(K).entrySet());
        
        int maxTime = 0;
        
        while (!queue.isEmpty()) {
            Map.Entry<Integer, Integer> entry = queue.poll();
            int node = entry.getKey();
            int time = entry.getValue();
            
            if (timeMap.containsKey(node)) {
                continue;
            }
            
            timeMap.put(node, time);
            maxTime = Math.max(maxTime, time);
            
            for (Map.Entry<Integer, Integer> next : graph.get(node).entrySet()) {
                next.setValue(next.getValue() + time);
                queue.offer(next);
            }
        }
        
        return timeMap.size() == N - 1 ? maxTime : -1;  // in case there's a node that K cannot reach
    }
}