Dijkstra

import static java.lang.System.out;
/*
 *1-
0-1-
2-1-
8-2-1-
7-1-
5-2-1-
6-7-1-
3-2-1-
4-5-2-1-
 */
import java.io.File;
import java.util.PriorityQueue;
import java.util.Scanner;
/*
 * 0-
1-0-
7-0-
6-7-0-
5-6-7-0-
2-1-0-
8-2-1-0-
3-2-1-0-
4-5-6-7-0-
0 4 12 19 21 11 9 8 14 The updated list after finding shortest Path
[0, 1, 7, 6, 5, 2, 8, 3, 4]

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

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



    public static void main(String [] args) {
     try{
            Scanner scn=new Scanner(new File("C://Users//user//Desktop//Dijkstra.txt"));
            String[] splitA;

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

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


         //   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();
            }

     getShortestPath(1);
     }
            catch(Exception e) {
            e.printStackTrace();
            }
    }
    public static void sortQueue() {
        q.clear();
        for (int index = 0; index < node; index++) {
            if (color[index]==0) {
                q.add(d[index]);
            }
        }
    }
    public static void getShortestPath(int s) {
        for(int i=0;i<node;i++) {
            if (i != s) {
            d[i]=999;
             //q.add(d[i]);
            color[i]=0;
            parent[i]=-1;
        }
        }

    d[s]=0;
    parent[s]=-1;
    q.add(d[s]);
    int count=0;
    while (!(q.isEmpty())) {
        int u=findIndex(d,q.poll());
        //System.out.println(q.peek());
        //print();
        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.print(vertices[u]+"=>");
        printPath(u);
     sortQueue();
     count++;
    }
    print();
    printCost();
    }
    public static void printPath(int node){
        int x=node;

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

        }
        out.println();
    }

    public static void printCost() {
        for(int m=0;m<node;m++) {
            System.out.print(m+"=>" +d[m]+"$ ,");
    }
    }

    public static void print() {
         System.out.println();
         System.out.println();
         for(int c=0;c<node;c++) {

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

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

     public static int findIndex(int arr[], int t)
        {

            // if array is Null
            if (arr == null) {
                return -1;
            }

            // find length of array
            int len = arr.length;
            int i = 0;

            // traverse in the array
            while (i < len) {

                // if the i-th element is t
                // then return the index
                if (arr[i] == t && color[i]==0) {
                    return i;
                }
                else {
                    i = i + 1;
                }
            }
            return -1;
        }
}