fork(1) download
copy 
  1. import java.util.*;
  2.  
  3. /**
  4.  * Created by Shreyans on 4/21/2015 at 6:32 PM using IntelliJ IDEA (Fast IO Template)
  5.  */
  6.  
  7. //ADD PUBLIC FOR CF,TC
  8. class DIJKSTRA
  9. {
  10.     public static void main(String[] args) throws Exception
  11.     {
  12.         Scanner sc=new Scanner(System.in);
  13.         List<ArrayList<Node>> gr=new ArrayList<ArrayList<Node>>();//Initialising Adj list to store graph
  14.         //System.out.println("Enter Number of Vertices");
  15.         int v=sc.nextInt();
  16.         for(int i=0;i<=v;i++)
  17.         {
  18.             gr.add(new ArrayList<Node>());
  19.         }
  20.         //System.out.println("Enter Number of Edges");
  21.         int e=sc.nextInt();
  22.         //System.out.println("Enter <Vertex> <Adjacent Vertex> <Weight>");
  23.         for(int i=0;i<e;i++)
  24.         {
  25.             int a=sc.nextInt();
  26.             int b=sc.nextInt();
  27.             int c=sc.nextInt();
  28.             gr.get(a).add(new Node(b,c));
  29.         }//Built Graph
  30.         //System.out.println("Enter Source");
  31.         int s=sc.nextInt();
  32.         //int des=sc.nextInt();//Entering Destination
  33.         Queue<Node> pq=new PriorityQueue<Node>(new Node());//Heap to extract value
  34.         Set<Integer>ch=new HashSet<Integer>();//Set to keep track of checked values
  35.         int[]d=new int[v+1];//Keeping track of distances
  36.         Arrays.fill(d,Integer.MAX_VALUE);
  37.         d[s]=0;
  38.         pq.clear();
  39.         pq.add(new Node(s,0));
  40.         while(!pq.isEmpty())
  41.         {
  42.             Node x=pq.poll();
  43.             int V=x.node;//Getting next node from heap
  44.             int W=x.cost;//Getting cost
  45.             ch.add(V);//Adding vertex to checked
  46.             for(int i=0;i<gr.get(V).size();i++)
  47.             {
  48.                 Node z=gr.get(V).get(i);//Getting all adjacent Vertices
  49.                 if(!ch.contains(z.node))//Not checking visited Vertices
  50.                 {
  51.                     int v1=z.node;
  52.                     int w1=z.cost;
  53.                     if(d[v1]>W+w1)//Checking for min weight
  54.                     {
  55.                         d[v1]=W+w1;
  56.                     }
  57.                     pq.offer(new Node(v1,d[v1]));//Adding element to PriorityQueue
  58.                 }
  59.             }
  60.         }
  61.         for(int i=1;i<=v;i++)//Printing Shortest Distances. Ignore ones with Integer.MAV_VALUE. Meh
  62.         {
  63.             if(d[i]==Integer.MAX_VALUE)
  64.             {
  65.                 System.out.println("No Path connecting Source Vertex "+s+" to Vertex "+i);
  66.             }
  67.             else
  68.             {
  69.                 System.out.println("Shortest distance from  Source Vertex "+s+" to Vertex "+i+" is: "+d[i]);
  70.             }
  71.         }
  72.     }
  73. }
  74. class Node implements Comparator<Node>
  75. {
  76.     public int node;
  77.     public int cost;
  78.  
  79.     public Node(){}
  80.  
  81.     public Node(int node, int cost)
  82.     {
  83.         this.node = node;
  84.         this.cost = cost;
  85.     }
  86.  
  87.     @Override
  88.     public int compare(Node node1, Node node2)
  89.     {
  90.         if (node1.cost < node2.cost)
  91.             return -1;
  92.         if (node1.cost > node2.cost)
  93.             return 1;
  94.         return 0;
  95.     }
  96. }
Success #stdin #stdout 0.15s 321088KB
comments (?)
stdin
copy 
3 3
1 2 4
1 3 7
2 3 1
1
stdout
copy 
Shortest distance from  Source Vertex 1 to Vertex 1 is: 0
Shortest distance from  Source Vertex 1 to Vertex 2 is: 4
Shortest distance from  Source Vertex 1 to Vertex 3 is: 5
https://ideone.com/NBKrYc
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!