1
\$\begingroup\$

I was attempting a question on HackerRank-Dijkstra's Shortest Reach 2 and upon submission my programs times out in 3/7 test cases. One of the test cases had 200 nodes and about 2000 connections. Here is my code-

  import java.util.Comparator;
  import java.util.PriorityQueue;
  import java.util.Scanner;
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.io.IOException;
  import java.util.HashMap;
  import java.util.Map;
  import java.io.DataInputStream;
  import java.io.FileInputStream;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.Scanner;
  import java.util.StringTokenizer;
  import java.util.ArrayList;
  import java.util.Iterator;



class Node implements Comparator<Node>{
int cost, node;
Node(){}
Node(int node, int cost){
    this.node=node;
    this.cost=cost;
}
@Override
public int compare(Node n1, Node n2){
    if(n1.cost<n2.cost)return -1;
    else if(n1.cost>n2.cost)return 1;
     return 0;
  }
}
   class Solution {
 // Working program using Reader Class
 static int adjmatrix[][];
 static PriorityQueue<Node> pq;
 static boolean visited[];
 static int distance[];
 @SuppressWarnings("unchecked")
 static ArrayList<Map<Integer,Integer>> list;


     static class Reader
     {
         final private int BUFFER_SIZE = 1 << 16;
         private DataInputStream din;
         private byte[] buffer;
         private int bufferPointer, bytesRead;

         public Reader()
         {
             din = new DataInputStream(System.in);
             buffer = new byte[BUFFER_SIZE];
             bufferPointer = bytesRead = 0;
         }

         public Reader(String file_name) throws IOException
         {
             din = new DataInputStream(new FileInputStream(file_name));
             buffer = new byte[BUFFER_SIZE];
             bufferPointer = bytesRead = 0;
         }

         public String readLine() throws IOException
         {
             byte[] buf = new byte[64]; // line length
             int cnt = 0, c;
             while ((c = read()) != -1)
             {
                 if (c == '\n')
                     break;
                 buf[cnt++] = (byte) c;
             }
             return new String(buf, 0, cnt);
         }

         public int nextInt() throws IOException
         {
             int ret = 0;
             byte c = read();
             while (c <= ' ')
                 c = read();
             boolean neg = (c == '-');
             if (neg)
                 c = read();
             do
             {
                 ret = ret * 10 + c - '0';
             }  while ((c = read()) >= '0' && c <= '9');

             if (neg)
                 return -ret;
             return ret;
         }

         public long nextLong() throws IOException
         {
             long ret = 0;
             byte c = read();
             while (c <= ' ')
                 c = read();
             boolean neg = (c == '-');
             if (neg)
                 c = read();
             do {
                 ret = ret * 10 + c - '0';
             }
             while ((c = read()) >= '0' && c <= '9');
             if (neg)
                 return -ret;
             return ret;
         }

         public double nextDouble() throws IOException
         {
             double ret = 0, div = 1;
             byte c = read();
             while (c <= ' ')
                 c = read();
             boolean neg = (c == '-');
             if (neg)
                 c = read();

             do {
                 ret = ret * 10 + c - '0';
             }
             while ((c = read()) >= '0' && c <= '9');

             if (c == '.')
             {
                 while ((c = read()) >= '0' && c <= '9')
                 {
                     ret += (c - '0') / (div *= 10);
                 }
             }

             if (neg)
                 return -ret;
             return ret;
         }

         private void fillBuffer() throws IOException
         {
             bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
             if (bytesRead == -1)
                 buffer[0] = -1;
         }

         private byte read() throws IOException
         {
             if (bufferPointer == bytesRead)
                 fillBuffer();
             return buffer[bufferPointer++];
         }

         public void close() throws IOException
         {
             if (din == null)
                 return;
             din.close();
         }
     }
   ////////////////////////////////////////////////
 public static void initialize(int n){
    // adjmatrix=new int[n+1][n+1];
     visited=new boolean[n+1];
     distance=new int[n+1];
     list=new ArrayList<>(n+1);
     pq=new PriorityQueue<>(n+1,new Node());
     for(int i=1; i<=n+1; ++i)list.add(new HashMap<Integer, Integer>());
     for(int i=0; i<n+1; ++i)distance[i]=Integer.MAX_VALUE;
 }

     //////////////////////////////////////////////
    public static void shortestPath(int s){
       // int length=adjmatrix.length;
        int min_node;
        visited[s]=true;
        distance[s]=0;
        pq.add(new Node(s,0));
        while(!pq.isEmpty()){
            min_node=pq.remove().node;
            visited[min_node]=true;
            updateDistance(min_node);
        }
    }
    ///////////////////////////////////////////////
     //Using adjlist
    private static void updateDistance(int s){
        Map<Integer,Integer> current=list.get(s);
       // Iterator itr=current.entrySet().iterator();
       for(Map.Entry<Integer, Integer> entry:current.entrySet()){
            int node=entry.getKey();
            int cost=entry.getValue();
            if(!visited[node]){

                    distance[node]=Math.min(cost+distance[s], distance[node]);
                    pq.add(new Node(node,distance[node]));

            }
        }

    }

         ////////////////////////////////////////////////////////////////
     public static void main(String []args)throws IOException{
         Reader r=new Reader();
         //StringBuilder sb = new StringBuilder();


         int T=r.nextInt(), N, M;
         for(int caseNo=1; caseNo<=T; ++caseNo){
              initialize(3000);
             N=r.nextInt();
             //initialization

             //initialization of adjacecny matrix



             M=r.nextInt();
             //list=new ArrayList<>(N+1);


             for(int j=1; j<=M; ++j){

                     int node1=r.nextInt();
                     int node2=r.nextInt();
                     int distance=r.nextInt();

                     if(list.get(node1).get(node2)!=null){
                         int temp=list.get(node1).get(node2);
                         if(temp<distance)continue;
                     }

                     list.get(node1).put(node2,distance);
                     list.get(node2).put(node1, distance);

             }

             //end of graph initialization as a hybrid of adjmatrix and adjlist

            int s=r.nextInt();
             shortestPath(s);

             for(int i=1; i<=N; ++i)if(i!=s)System.out.print(((distance[i]==Integer.MAX_VALUE)?-1:distance[i])+" ");
             System.out.println();
         }//end of test cases loop[
     }
}

So how can I optimize this code? Here is the link to the question- https://www.hackerrank.com/challenges/dijkstrashortreach

\$\endgroup\$
4
\$\begingroup\$

Reject nodes already visited

Your main loop looks like this:

while(!pq.isEmpty()){
    min_node=pq.remove().node;
    visited[min_node]=true;
    updateDistance(min_node);
}

Since your code is capable of adding the same node multiple times to the priority queue (with updated costs), you should reject any node that you've already visited, like this:

while(!pq.isEmpty()){
    min_node=pq.remove().node;
    if (visited[min_node])
        continue;
    visited[min_node]=true;
    updateDistance(min_node);
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Indeed, it's not a proper implementation of Dijkstra's algorithm if a node that has already been visited can be re-visited. \$\endgroup\$ – PellMel Oct 26 '16 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.