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

• 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;
}
``````

• 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.

• This post is deleted!

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

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