Run-error in "Dijkstra's Algorithm" problem

#1

MY CODE IS PASSING THE SAMPLE TEST CASE AND MANY OTHER CASES BUT ON SUBMISSION, IT IS SHOWING ‘RUN ERROR’.
I AM POSTING ONLY THE CONCERNED FUNCTION. REST ALL THE CLASSES AND FUNCTIONS USED ARE WORKING FINE. PLEASE TELL ME WHERE I AM DOING MISTAKE.

public HashMap<Integer,Integer> dijkstra(int src,Graph graph)
{
HashMap<Integer,Integer> ans=new HashMap<>();
HashMap<Integer,DijkstraPair> map=new HashMap<>();
HeapGeneric heap=new HeapGeneric<>();
for(Integer key:graph.vtces.keySet())
{
DijkstraPair np=new DijkstraPair();
np.vname=key;
np.psf="";
np.cost=Integer.MAX_VALUE;
if(key.equals(src))
{
np.cost=0;
np.psf=key+"";
}
heap.add(np);
map.put(key, np);
}
HashMap<Integer,Boolean> updated=new HashMap<>();
while(!heap.isEmpty())
{
DijkstraPair rp=heap.remove();
map.remove(rp.vname);
ans.put(rp.vname,rp.cost);
int flag=0;
for(Integer nbr:graph.vtces.get(rp.vname).nbrs.keySet())
{
if(map.containsKey(nbr))
{
flag++;
int oc=map.get(nbr).cost;
int nc=rp.cost+graph.vtces.get(rp.vname).nbrs.get(nbr);
if(oc>nc)
{
DijkstraPair gp=map.get(nbr);
gp.psf=rp.psf+nbr;
gp.cost=nc;
updated.put(nbr,true);
heap.updatePriority(gp);
}
}
}
if(flag==0)
{
ArrayList keys=new ArrayList<>(map.keySet());
for(Integer key:keys)
{
if(!updated.containsKey(key))
{
ans.put(key,-1);
map.get(key).cost=-1;
heap.remove();
}
}
}
}
return ans;
}

#2

@vinay86048,

In this problem, for a given graph G with N vertices, M undirected edges with integer weights between them, and special vertex S, the goal is to find the length of the shortest paths from S to each of all N vertices.

If all edges of G have non-negative weights, the most well-known and also widely used method of solving this problem is to use Dijkstra’s algorithm implemented with a priority queue. In that case, the total time complexity of the algorithm is O(MlogN). This is true because each edge of the graph is examined exactly once, and such an examination can cause a constant number of updates in a priority queue containing either O(N) or O(M) vertices depending on the implementation. However, since each such operation on a priority queue has complexity proportional to the logarithm of its size, it does not matter if the queue contains O(N) or O(M) entries, since logM <= 2logN because M is at most N2 in this problem.

Try to use arrays instead of maps.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.