743.Network Delay Time

https://leetcode.com/problems/network-delay-time/solution/ 1-Dijkstra - ON^2

Learn How to construct weighed graph and how to implement Dijkstra algorithm.

class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        int[] distance = new int[N + 1];
        boolean[] seen = new boolean[N + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        Map<Integer, List<int[]>> graph = new HashMap<>();
        //Construct Graph
        for(int[] edge : times){
            if(!graph.containsKey(edge[0])){
                graph.put(edge[0], new ArrayList<>());
            }
            List<int[]> list = graph.get(edge[0]);
            list.add(new int[]{edge[1], edge[2]});
        }
        distance[K] = 0;
        while(true){
            int candNode = -1;
            int candDist = Integer.MAX_VALUE;
            for(int i = 1; i <= N; i++){
                //Select Min Node;
                if(!seen[i] && distance[i] < candDist){
                    candDist = distance[i];
                    candNode = i;
                }
            }

            if(candNode < 0)
                break;
            seen[candNode] = true;
            if(graph.containsKey(candNode)){
                for(int[] info : graph.get(candNode)){
                    distance[info[0]] = Math.min(distance[candNode] + info[1], distance[info[0]]);
                }
            }
        }
        int ans = 0;
        //Check if can reach all the node;
        for(int i = 1; i <= N; i++){
            if(distance[i] == Integer.MAX_VALUE){
                ans = -1;
                break;
            }
            ans = Math.max(ans, distance[i]);
        }
        return ans;
    }
}

2-Using Heap for Dijkstra

class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        Map<Integer, List<int[]>> graph = new HashMap<>();
        //Construct Graph
        for(int[] edge : times){
            if(!graph.containsKey(edge[0])){
                graph.put(edge[0], new ArrayList<>());
            }
            List<int[]> list = graph.get(edge[0]);
            list.add(new int[]{edge[1], edge[2]});
        }
        Map<Integer, Integer> distance = new HashMap<>();
        PriorityQueue<int[]> heap = new PriorityQueue<int[]>((int[] info1, int[] info2) -> (info1[1] - info2[1]));
        heap.offer(new int[]{K, 0});
        while(!heap.isEmpty()){
            int[] info = heap.poll();
            int dist = info[1];
            int node = info[0];
            if(distance.containsKey(node))
                continue;
            distance.put(node, dist);
            if(graph.containsKey(node)){
                for(int[] currentInfo : graph.get(node)){
                    if(!distance.containsKey(currentInfo[0])){
                        heap.offer(new int[]{currentInfo[0], currentInfo[1] + dist});
                    }
                }
            }
        }
        if(distance.size() != N)
            return -1;
        int ans = 0;
        for(int dist : distance.values()){
            ans = Math.max(ans, dist);
        }
        return ans;
    }
}