# Dijkstra's Algorithm not optimized enough

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.IOException;
import java.util.HashMap;
import java.util.Map;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
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 PriorityQueue<Node> pq;
static boolean visited[];
static int distance[];
@SuppressWarnings("unchecked")
static ArrayList<Map<Integer,Integer>> list;

{
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;

{
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
}

{
din = new DataInputStream(new FileInputStream(file_name));
buffer = new byte[BUFFER_SIZE];
}

{
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;
while (c <= ' ')
boolean neg = (c == '-');
if (neg)
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;
while (c <= ' ')
boolean neg = (c == '-');
if (neg)
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;
while (c <= ' ')
boolean neg = (c == '-');
if (neg)

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
{
buffer[0] = -1;
}

{
fillBuffer();
return buffer[bufferPointer++];
}

public void close() throws IOException
{
if (din == null)
return;
din.close();
}
}
////////////////////////////////////////////////
public static void initialize(int n){
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 min_node;
visited[s]=true;
distance[s]=0;
while(!pq.isEmpty()){
min_node=pq.remove().node;
visited[min_node]=true;
updateDistance(min_node);
}
}
///////////////////////////////////////////////
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]);

}
}

}

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

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

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

}

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

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);
}

• Indeed, it's not a proper implementation of Dijkstra's algorithm if a node that has already been visited can be re-visited. Oct 26, 2016 at 19:28