Dijkstra_2020

/*
 * 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 Lab6_Dijkstra;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;


/**
 *
 * @author acer
 */
public class Dijkstra {
    public static int node;
    public static int [] d;
    public static int [] parent;
    public static int [] [] matrix;
     public static int [] color;

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


    public static void main(String[] args) {
  //float a=0;
        try{
            Scanner scn=new Scanner(new File("F:\\CSE_BRACU\\Courses_TAKEN\\LABS\\Algorithm_221\\Ins.txt"));
            String[] splitA;


            node=Integer.parseInt(scn.nextLine());


            int edge=Integer.parseInt(scn.nextLine());


         //   out.println(v);
            matrix=new int[node][node];
            color=new int[node];
            parent=new int[node];
            d=new int[node];
            while(scn.hasNext())
            {
            String line=scn.nextLine();
            splitA=line.split(",");
            int x=Integer.parseInt(splitA[0]);
            int y=Integer.parseInt(splitA[1]);
            int w=Integer.parseInt(splitA[2]);
            matrix[x][y]=w;
            matrix[y][x]=w;
            }
         for(int i=0;i<node;i++) {
                for(int j=0;j<node;j++) {
                    System.out.print(matrix[i][j]+",");
                }
                System.out.println();
            }


        } catch (Exception ex) {
            ex.printStackTrace();
        }
        dijkstra(0);


    }
    public static void dijkstra(int s) {


       for(int i=0;i<node;i++) {

            d[i]=999;
             //q.add(d[i]);
            color[i]=0;
            parent[i]=-1;

        }

    d[s]=0;
    parent[s]=-1;
    q.add(d[s]);

    while (!(q.isEmpty())) {
        int u=findIndex(q.poll(),d);
        //System.out.println(q.peek());
        //print();

        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;

                 }
                }
            }
        }
        color[u]=1;
        queueSort();
        System.out.println("for node "+u+": ");

     printPath(u);
     //findPath(u);


    }

    }
         public static int findIndex(int value,int [] arr) {
         int index=-1;
         for(int i=0;i<arr.length;i++){
             if(value==arr[i] ){
                 index=i;
             }
         }
        return index;
    }

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

        }

       }
          //System.out.println("queue"+q.toString());


    }

     /*public static void findPath(int x) {

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

    }*/

     public static void printPath(int node){
        int x=node;

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

        }
        System.out.println();
    }
}