743. Network Delay Time

Link

Solution

PriorityQueue + BFS的運用

用PriorityQueue將總距離最短的路線先進行檢查，看何時能把Node都尋找完畢。此時完成最後一個node的路線就是最短的路線。

public int networkDelayTime(int[][] times, int N, int K) {
        HashMap<Integer, Map<Integer, Integer>> map = new HashMap<>();
        for(int i = 0; i < times.length; i++){
            int[] time = times[i];
            map.compute(time[0], (k,v)->{
                if(v == null){
                   HashMap<Integer, Integer> value = new HashMap<>();
                   value.put(time[1], time[2]);
                   return value;
                } 
                v.put(time[1], time[2]);
                return v;
            });
        }
        //map : key -> start node
        //      value -> another map : key -> end node 
        //                             value -> distance
        
        boolean[] visited = new boolean[N+1];
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)-> a[0]-b[0]);
        pq.add(new int[]{0, K}); // {distance, curNode}
        int ret = 0;
        while(!pq.isEmpty()){
            int[] node = pq.poll();
            int curDist = node[0];
            int curNode = node[1];
            if(visited[curNode]) continue;
            visited[curNode] = true;
            N--;
            ret = curDist;
            if(N == 0) return ret;
            if(map.containsKey(curNode)){
                for(Integer key : map.get(curNode).keySet()){
                    //add the possible path to the pq
                    pq.add(new int[]{curDist + map.get(curNode).get(key), key} );
                }
            }
            
        }
        return -1;
    }