Trying to implement Dijsktra in Java using priority queue and using hash map for decrease key

Full Disclosure - I am doing this exercise to solve this problem on Leetcode - https://leetcode.com/problems/network-delay-time/

I find that this code is not working for certain test cases. I have been trying to debug this for a few hours havent had any luck. Can anyone help the bug in this code.

// this has a bug which I dont know how to find
public int networkDelayTime(int[][] times, int N, int K) {
Map<Integer, Map<Integer,Integer>> adjListWithDistance = new HashMap<>();
// using this distance Map from K as comparator in priority queue
Map<Integer, Integer> dMapFromK = new HashMap<>();
PriorityQueue<Integer> pq = new PriorityQueue<>((k1,k2) -> dMapFromK.get(k1) - dMapFromK.get(k2));
HashSet<Integer> v = new HashSet<>();
for(int i = 0; i < times.length; i++){
int source = times[i][0];
int dest = times[i][1];
int dist = times[i][2];
adjListWithDistance.putIfAbsent(source, new HashMap<>());
adjListWithDistance.get(source).put(dest, dist);
//if(source == K){
//    dMapFromK.put(dest, dist);
//    pq.add(dest);
// }
}
// distance from K to K is 0
dMapFromK.put(K, 0);
pq.add(K);
// we have already added all nodes from K to PQ, so we dont need to process K again
//v.add(K);
//System.out.println(adjListWithDistance);
//System.out.println(dMapFromK);
int res = 0;
while(!pq.isEmpty()){
int fromNode = pq.poll();
if(v.contains(fromNode)) continue;
v.add(fromNode);
int curDist = dMapFromK.get(fromNode);
res = curDist;
//System.out.println("current node - " + fromNode);
if(!adjListWithDistance.containsKey(fromNode)) {
continue;
}
for(Integer toNode: adjListWithDistance.get(fromNode).keySet()){
// BIG BUGGGGG, adding the below line is also causing a bug , not sure why
if(v.contains(toNode)) continue;
int toNodeDist = adjListWithDistance.get(fromNode).get(toNode);
if(dMapFromK.containsKey(toNode) && dMapFromK.get(toNode) <= curDist + toNodeDist){
continue;
}else {
if(!dMapFromK.containsKey(toNode)){
dMapFromK.put(toNode, curDist + toNodeDist);
// need to add map entry first before adding to priority queue else it throws an exception
pq.offer(toNode);
}else{
dMapFromK.put(toNode, curDist + toNodeDist);
}
}
}
}
System.out.println(adjListWithDistance);
System.out.println(dMapFromK);
if(dMapFromK.keySet().size() != N)
return -1;
//return res;
return Collections.max(dMapFromK.values());
}

TLDR: This implementation of Dijsktra is not correct and doesn't return the shortest path for certain nodes for certain test cases. I'm not sure why, and I need help debugging what mistake I am making.

This is almost the same, will pass through:

public final class Solution {
public static final int networkDelayTime(
final int[][] times,
int n,
final int k
) {
Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
for (final int[] node : times) {
graph.putIfAbsent(node[0], new HashMap<>());
graph.get(node[0]).put(node[1], node[2]);
}
Queue<int[]> queue = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
queue.add(new int[] {0, k});
boolean[] visited = new boolean[n + 1];
int total = 0;
while (!queue.isEmpty()) {
int[] curr = queue.remove();
int currNode = curr[1];
int currTime = curr[0];
if (visited[currNode]) {
continue;
}
visited[currNode] = true;
total = currTime;
n--;
if (graph.containsKey(currNode)) {
for (final int next : graph.get(currNode).keySet()) {
queue.add(new int[] {currTime + graph.get(currNode).get(next), next});
}
}
}
return n == 0 ? total : -1;
}
}

Here is a Python version using heap, if you'd be interested:

from typing import List
import heapq
from collections import defaultdict
class Solution:
def networkDelayTime(self, times: List[List[int]], n, k) -> int:
queue = [(0, k)]
graph = collections.defaultdict(list)
memo = {}
for u_node, v_node, time in times:
graph[u_node].append((v_node, time))
while queue:
time, node = heapq.heappop(queue)
if node not in memo:
memo[node] = time
for v_node, v_time in graph[node]:
heapq.heappush(queue, (time + v_time, v_node))
return max(memo.values()) if len(memo) == n else -1

In C++, we'd just use a fast integer type:

// The following block might trivially improve the exec time;
// Can be removed;
static const auto __optimize__ = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
return 0;
}();
// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <vector>
#include <algorithm>
#define MAX INT_MAX
using ValueType = std::uint_fast16_t;
static const struct Solution {
static const int networkDelayTime(
const std::vector<vector<int>>& times, 
int n, 
const int k
) {
std::vector<ValueType> distances(n + 1, MAX);
distances[k] = 0;
for (ValueType index = 0; index < n; index++) {
for (const auto& time : times) {
const ValueType u_node = time[0];
const ValueType v_node = time[1];
const ValueType uv_weight = time[2];
if (distances[u_node] != MAX && distances[v_node] > distances[u_node] + uv_weight) {
distances[v_node] = distances[u_node] + uv_weight;
}
}
}
ValueType total_time = 0;
for (auto index = 1; index <= n; index++) {
total_time = std::max(total_time, distances[index]);
}
return total_time == MAX ? -1 : total_time;
}
};

References

• For additional details, please see the Discussion Board where you can find plenty of well-explained accepted solutions with a variety of languages including low-complexity algorithms and asymptotic runtime/memory analysis^{1, 2}.