 # Dijkastra Algorithm - (Solved)

I was learning dijkastra algorithm and created a very simple program. But I am facing TLE in one test case in hackerrank. Can you please check what I am doing wrong?

``````        //edges is 2d matrix having 3 coloumns [vertexA, vertexB, weight]
//s = source vertex
//n = total number of nodes

HashMap<Integer, ArrayList<Node>> hm = new HashMap<Integer, ArrayList<Node>>();
int e = edges.length;
for(int i=0;i<e;i++){
int u = edges[i];
int v = edges[i];
int d = edges[i];
if(!hm.containsKey(u)){
hm.put(u,new ArrayList<Node>());
}
if(!hm.containsKey(v)){
hm.put(v, new ArrayList<Node>());
}
}

System.out.println(hm);

PriorityQueue<Node> pq = new PriorityQueue<Node>();

//in central place

int d[] = new int[n+1];
for(int i=0;i<=n;i++){
d[i]=Integer.MAX_VALUE;
}
d[s]=0;

while(pq.size()>0){
Node u = pq.poll();
for(int i=0;i<hm.get(u.vertex).size();i++){
Node v = hm.get(u.vertex).get(i);
if(d[v.vertex]>d[u.vertex]+v.w){
d[v.vertex]=d[u.vertex]+v.w;
}
}
}
``````

Now, Integer array d will be having shortest path from source vertex to all other vertex.

Here is the full Code with problem link.
https://pastebin.com/2f3AwnGd

Possibly for using the hashset a lot, a better idea is to relabel the nodes at the time of reading to range 0 to n-1 (and just use these).

Thank for replying, I changed from hashmap to ArrayList, still facing Time out issue for testcase 7, seems like some problem in logic.

For those, who face some problem while solving question that uses dijkastra. So in dijkastra or specially in my above solution, I was not using visited list of vertexes. This is used to remove the uncessary steps for processing a node which is already into to priority queue having greater distance.