Dijkstra's Shortest Path-HackerRank

Question

I was solving the problem — Dijkstra's Shortest Reach 2. Here's a link.

Given a graph consisting N nodes (labelled 1 to N) where a specific given node S represents the starting position S and an edge between two nodes is of a given length, which may or may not be equal to other lengths in the graph.

It is required to calculate the shortest distance from the start position (Node S) to all of the other nodes in the graph.

Note: If a node is unreachable, the distance is assumed as — 1.

Input Format

The first line contains, denoting the number of test cases. First line of each test case has two integers, denoting the number of nodes in the graph and, denoting the number of edges in the graph.

The next lines each consist of three space-separated integers , where and denote the two nodes between which the undirected edge exists, denotes the length of edge between these corresponding nodes.

The last line has an integer, denoting the starting position.

Constraints

If there are edges between the same pair of nodes with different weights, they are to be considered as is, like multiple edges.

Output Format

For each of the test cases, print a single line consisting space separated integers denoting the shortest distance of nodes other than from starting position in increasing order of their labels.

For unreachable nodes, print.

Sample Input

1
4 4
1 2 24
1 4 20
3 1 3
4 3 12
1

Sample Output

24 3 15

And here is my code:

The Node class

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<>(new Node());
         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){
         N=r.nextInt();
         //initialization
         initialize(N);
         //initialization of adjacecny matrix



         M=r.nextInt();
         //list=new ArrayList<>(N+1);
        for(int i=1; i<=N+1; ++i)list.add(new HashMap<Integer, Integer>());

         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[
 }
 }

I apologize for the long code and the question. My program is working only for the sample test case. In the rest, it starts out correctly but by the end of the input it ends up giving a different answer. I can paste the copy of the expected input and output if needed. As far as I can tell, it is probably related to how I am handling the case of multiple undirected edges. I am only keeping the smaller edge.

P.S.-It is giving the correct values now but the speed isn't fast enough. Any optimization suggestions are welcome

Answer 1

On a first glance your code seems correct (although I'm no expert in Java).

Below is my code as reference (may give you an idea), & here is the link to the code in my github Dijkstra hackerrank

Actually it got accepted with the Queue version (you don't have to implement it with a minHeap - although minHeap version is more correct - O(E log V) instead of O(V^2).

Here is the queue version: Dijkstra queue version

#include <iostream>
#include <vector>
#include <utility>
#include <limits>
#include <memory>
#include <map>
#include <set>
#include <queue>
#include <stdio.h>


using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
const int max_int = 1 << 20; //numeric_limits<int>::max();


class Graph{
public:
    Graph(int nodes = 3000, int edges = 3000*3000/2):
        nodes_(nodes+1),
        edges_(edges),
        dist_(nodes+1, max_int),
        adjList_(nodes+1),
        in_queue_(nodes+1, 0)
    {
    }
    ~Graph() {}
    void addEdge(int from, int to, int w) {

        adjList_[from].emplace_back(ii(w, to));
        adjList_[to].emplace_back(ii(w, from));
    }
    vii getNeighbours(int n) {
        return adjList_[n];
    }
    void dijkstra(int src);

private:
    vi dist_;
    vector<vii> adjList_;
    int nodes_;
    int edges_;
    int src_;
    void print(int node);
    vi in_queue_;
   // queue<int> q_;
    std::priority_queue<ii, vii, greater<ii>> q_;
};

void Graph::dijkstra(int src)
{
    src_ = src;
    dist_[src] = 0;
    q_.push(make_pair(0, src)); in_queue_[src_] = 1;
    while(!q_.empty()) {
        auto front = q_.top();  q_.pop();
        int d = dist_[front.second], u = front.second;
        in_queue_[u] = 0;
            for(int i = 0 ; i < (int)adjList_[u].size(); ++i) {
                auto v = adjList_[u][i];
                if(dist_[v.second] > dist_[u] + v.first) {
                    dist_[v.second] = dist_[u] + v.first;
                    if(!in_queue_[v.second]) {
                        q_.push(make_pair(dist_[v.second], v.second));
                        in_queue_[v.second] = 1;
                    }
                }
            }
    }

    for(int i = 1; i < nodes_; ++i) {
        if(i == src_) {
            continue;
        }
        if(dist_[i] == max_int) {
            cout << "-1" << " ";
        }
        else{
            cout << dist_[i] << " ";
        }
    }
    cout << endl;
}



int main(){
     std::ios::sync_with_stdio(false); 
    int t;
    cin >> t;
    for(int a0 = 0; a0 < t; a0++){
        int n;
        int m;
        cin >> n >> m;
        unique_ptr<Graph> g(new Graph(n,m));
        for(int a1 = 0; a1 < m; a1++){
            int x;
            int y;
            int r;

            cin >> x >> y >> r;
            g->addEdge(x, y, r);
        }
        int s;
        cin >> s;
        //scanf("%d", &s);
        g->dijkstra(s);
    }
    return 0;
}