Dijkastra Algorithm - (Solved)

help
1

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.

2

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

3

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

4

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.