dijkstra2_updated

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package algorithm;


import java.io.File;
import java.util.HashSet;

import java.util.PriorityQueue;

import java.util.Scanner;

/**
 *
 * @author acer
 */
public class Algo_Dijkstra {
     public static int node;
     public static int edge;
    public static int[] color;
    public static int [] vertices={0,1,2,3,4,5,6,7,8};
    public static int [] d;
    public static int [] parent;
    public static int [][] matrix;
    public static int [] wt;

    public static PriorityQueue<Integer> q=new PriorityQueue<Integer>();

    public static void main (String [] args){
       try{
           Scanner sc=new Scanner(new File("E:\\Ins.txt"));
           String [] split;
           node=Integer.parseInt(sc.nextLine());
           edge=Integer.parseInt(sc.nextLine());
           matrix=new int [node][node];

           int count=0;
           while(sc.hasNext()){
               String line=sc.nextLine();
               split=line.split(",");
               int x=Integer.parseInt(split[0]);
               int y=Integer.parseInt(split[1]);
               int w=Integer.parseInt(split[2]);
               matrix[x][y]=w;
               matrix[y][x]=w;

           }

           printMatrix();

           d=new int[node];
           color=new int[node];
           parent=new int[node];


          dijkstra(0);
           System.out.println();
          for(int i=1;i<node;i++){
              getPath(i);
          }


       }
       catch(Exception e){
          e.printStackTrace();
       }
   }
    public static void dijkstra(int s) {
        System.out.println("Entered Method");
         for(int i=0;i<node;i++){
             if(i!=s){
            color[i]=0;//white
            d[i]=999;
            parent[i]=-1;
        }
         }
            //gray
            d[s]=0;
            parent[s]=-1;

            HashSet <Integer> set=new <Integer>HashSet();

            q.add(d[s]);


            while(!(q.isEmpty())){

               int u=findIndex(q.poll(),d);//min
                set.add(u);
                color[u]=1;

                for(int v=0;v<node;v++){
                    if(matrix[u][v]!=0){
                        if(color[v]==0){
                        if(d[v]>(d[u]+matrix[u][v])){

                            d[v]=d[u]+matrix[u][v];
                            parent[v]=u;
                            //System.out.println(vertices[v]);
                        }
                    }
                    }
            }

               color[u]=1;//black
                queueSort();
                if(q.peek()!=null){
                System.out.print(u+"->");
                }else{
                    System.out.print(u);
                }
                //print();
            }

            System.out.println(set.toString());

            for(int i:d){
                System.out.print(i+",");
            }

    }


    public static void queueSort(){
        q.clear();
        for(int i=0;i<node;i++){
            if(color[i]==0){
            q.add(d[i]);

        }
       }

    }

    public static void getPath(int dst) {
               int x=dst;
               System.out.println(" Total Cost for "+x+" is :"+d[x]);

        while(x!=-1 )
        {
            System.out.print(x+"<=");
            x=parent[x];

        }
        System.out.println();
    }





    public static void printMatrix() {
        for(int i=0;i<matrix.length;i++){
               for(int j=0;j<matrix.length;j++){
                   System.out.print(matrix[i][j]+" ");
               }
               System.out.println();
           }

    }
    public static int findIndex(int value,int [] arr) {
         int index=-1;
         for(int i=0;i<arr.length;i++){
             if(value==arr[i] && color[i]==0){
                 index=i;
             }
         }
        return index;
    }
     public static void print() {
         System.out.println();
         System.out.println();
         for(int c=0;c<node;c++) {

              if(color[c]!=0) {
                 System.out.print("Visited"+",");

             }
             else {
                 System.out.print("Undiscovered"+",");
             }
        }
         System.out.println();
        }

}