743. Network Delay Time

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:
N will be in the range [1, 100].
K will be in the range [1, N].
The length of times will be in the range [1, 6000].
All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 1 <= w <= 100.

Solution：Djikstra 最短路径

思路：

Time Complexity: O() Space Complexity: O()

Solution Code：

class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        if(times == null || times.length == 0){
            return -1;
        }
        
        // graph init
        Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
        for (int[] time : times) {
            if (!graph.containsKey(time[0])) {
                graph.put(time[0], new HashMap<>());
            }
            graph.get(time[0]).put(time[1], time[2]);
            
        }

        // Djikstra init
        // for each node (bfs: queue):
        //   : calc the [shortest distance from the source node] from the neighbors, saved in distanceMap
        Queue<int[]> queue = new LinkedList<>(); // (nodeId, distance from source node)
        Map<Integer, Integer> distanceMap = new HashMap<>();
        distanceMap.put(K, 0); // source node
        int gLongest = -1;

        // // Djikstra start
        queue.offer(new int[]{K, 0});
        while (!queue.isEmpty()){
            int[] cur = queue.poll();
            int node = cur[0];
            int distance = cur[1];

            // ignore processed nodes
            if (distanceMap.containsKey(node) && distanceMap.get(node) < distance){
                continue;
            }
            
            Map<Integer, Integer> neighborsMap = graph.get(node);
            if (neighborsMap == null){
                continue;
            }

            for (int neighborId: neighborsMap.keySet()){
                int absoluteDistence = distance + neighborsMap.get(neighborId);
                if (distanceMap.containsKey(neighborId) && distanceMap.get(neighborId) <= absoluteDistence){
                    continue;
                }
                distanceMap.put(neighborId, absoluteDistence);
                queue.offer(new int[]{neighborId, absoluteDistence});
            }
        }
        // get the largest absolute distance.
        for (int val : distanceMap.values()){
            if (val > gLongest){
                gLongest = val;
            }
        }
        return distanceMap.size() == N ? gLongest : -1;
    }
}