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
//creating an adjancy list
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][0];
int v = edges[i][1];
int d = edges[i][2];
if(!hm.containsKey(u)){
hm.put(u,new ArrayList<Node>());
}
hm.get(u).add(new Node(v,d));
if(!hm.containsKey(v)){
hm.put(v, new ArrayList<Node>());
}
hm.get(v).add(new Node(u,d));
}
System.out.println(hm);
PriorityQueue<Node> pq = new PriorityQueue<Node>();
pq.add(new Node(s,0));
//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;
pq.add(v);
}
}
}
Now, Integer array d will be having shortest path from source vertex to all other vertex.
Here is the full Code with problem link.