Simple JAVA Djikstra's (PriorityQueue optimized) Solution with explanation


  • 12
    S

    It is a direct graph.

    1. Use Map<Integer, Map<Integer, Integer>> to store the source node, target node and the distance between them.
    2. Offer the node K to a PriorityQueue.
    3. 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.
    4. Return the node with the largest absolute distance.
    public int networkDelayTime(int[][] times, int N, int K) {
            if(times == null || times.length == 0){
                return -1;
            }
            // store the source node as key. The value is another map of the neighbor nodes and distance.
            Map<Integer, Map<Integer, Integer>> path = new HashMap<>();
            for(int[] time : times){
                Map<Integer, Integer> sourceMap = path.get(time[0]);
                if(sourceMap == null){
                    sourceMap = new HashMap<>();
                    path.put(time[0], sourceMap);
                }
                Integer dis = sourceMap.get(time[1]);
                if(dis == null || dis > time[2]){
                    sourceMap.put(time[1], time[2]);
                }
                
            }
    
            //Use PriorityQueue to get the node with shortest absolute distance 
            //and calculate the absolute distance of its neighbor nodes.
            Map<Integer, Integer> distanceMap = new HashMap<>();
            distanceMap.put(K, 0);
            PriorityQueue<int[]> pq = new PriorityQueue<>((i1, i2) -> {return i1[1] - i2[1];});
            pq.offer(new int[]{K, 0});
            int max = -1;
            while(!pq.isEmpty()){
                int[] cur = pq.poll();
                int node = cur[0];
                int distance = cur[1];
    
                // Ignore processed nodes
                if(distanceMap.containsKey(node) && distanceMap.get(node) < distance){
                    continue;
                }
                
                Map<Integer, Integer> sourceMap = path.get(node);
                if(sourceMap == null){
                    continue;
                }
                for(Map.Entry<Integer, Integer> entry : sourceMap.entrySet()){
                    int absoluteDistence = distance + entry.getValue();
                    int targetNode = entry.getKey();
                    if(distanceMap.containsKey(targetNode) && distanceMap.get(targetNode) <= absoluteDistence){
                        continue;
                    }
                    distanceMap.put(targetNode, absoluteDistence);
                    pq.offer(new int[]{targetNode, absoluteDistence});
                }
            }
            // get the largest absolute distance.
            for(int val : distanceMap.values()){
                if(val > max){
                    max = val;
                }
            }
            return distanceMap.size() == N ? max : -1;
    }
    

  • 0
    D

    In the solution above, will your priority queue potentially hold multiple copies of a node, with different absolute distances from the source? It seems you don't implement a decrese-key operation, but instead add a new element to the queue for the same node, but with a smaller distance so that it is picked up first.


  • 0
    S
    This post is deleted!

  • 0
    S

    @dribvurhd
    You are right. I just modified my code.
    Thank you very much for your comment.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.