Dijkstra's algorithm : graph Shortest Path implementation using java

Input Format

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

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

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


Example:
1
4 4
1 2 24
1 4 20
3 1 3
4 3 12
1




Output Format

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

For unreachable nodes, print -1.

Example:

24 3 15

Explanation

The straight line is a weighted edge, denoting length of edge between the corresponding nodes.
The nodes S,B,C and D denote the obvious node 1,2,3 and 4 in the test case.
The shortest paths followed for the three nodes B,C and D are as follows :

S->B - Shortest Path Value : 24

S->C - Shortest Path Value : 3

S->C->D - Shortest Path Value : 15


Program:

1. import java.io.*;
2. import java.util.*;
3. import java.text.*;
4. import java.math.*;
5. import java.util.regex.*;
6. 
   
7. class Node implements Comparable<Node>{
8.     int val, cost;
9.     Node(int val, int cost){
10.         this.val = val; this.cost = cost;
11.     }
12.     
13.     public int compareTo(Node x){
14.         return Integer.compare(this.cost, x.cost);
15.     }
16. }
17. 
    
18. public class Solution {
19. 
    
20.     public static void main(String[] args) {
21.         Scanner sc = new Scanner(System.in);
22.         int t = sc.nextInt();
23.         while(t-- > 0){
24.             int n = sc.nextInt(), m = sc.nextInt();
25.             ArrayList<ArrayList<Node>> adj = new ArrayList<ArrayList<Node>>(n+1);
26.             for(int i=0; i<n+1; i++)adj.add(new ArrayList<Node>(n+1));
27.         
28.             while(m-- > 0){
29.                 int x = sc.nextInt(), y = sc.nextInt(), cost = sc.nextInt();
30.                 adj.get(x).add(new Node(y, cost));
31.                 adj.get(y).add(new Node(x, cost));
32.             }
33.             int s = sc.nextInt();
34.             djikstra(s, adj, n);
35.         }
36.     }
37.     
38.     static void djikstra(int s, ArrayList<ArrayList<Node>> adj, int n){
39.         int[] dist = new int[n+1];
40.         Arrays.fill(dist, Integer.MAX_VALUE);
41.         dist[s] = 0;
42.         PriorityQueue<Node> pq = new PriorityQueue<Node>();
43.         pq.add(new Node(s, 0));
44.         while(pq.size() > 0){
45.             Node curr = pq.peek(); pq.remove();
46.             int currN = curr.val;
47.             Iterator<Node> it = adj.get(currN).iterator();
48.             while(it.hasNext()){
49.                 Node temp = it.next();
50.                 if(dist[temp.val] > dist[currN] + temp.cost){
51.                     pq.add(new Node(temp.val, dist[currN]+temp.cost));
52.                     dist[temp.val] = dist[currN] + temp.cost;
53.                 }
54.             }
55.         }
56.         
57.         for(int i=1; i<dist.length; i++){
58.             if(i!=s){
59.                 System.out.print(((dist[i] == Integer.MAX_VALUE)?-1:dist[i]) + " ");
60.             }
61.         }
62.         System.out.println();
63.     }
64. }