import java.util.LinkedList;


public class Graph {
    private double[][] path;
    private double[] weight;

    private int []parent;

    public Graph(double [][]path){
        this.path=path;
    }
    public Graph(int numberOfNode,double maximumDistance){
        this.path=new double[numberOfNode][numberOfNode];
        for(int i=0;i<path.length-1;i++){
            path[i][i]=0;
            for(int j=i+1;j<path[i].length;j++){
                path[i][j]=Math.random()*maximumDistance;
                path[j][i]=path[i][j];
            }
        }
    }
    public double getShortestDistanceTo(int goal){
        if(weight!=null){
            return weight[goal];
        }

        return 0;
    }
    public Object []getPathTo(int goal){
        if(weight!=null){
            int root=goal;
            LinkedList <Integer>list=new LinkedList<Integer>();
            while(parent[root]!=root){
                list.add(0,root);
                root=parent[root];
            }
            list.add(0,root);
            return list.toArray();
        }

        return null;
    }
    public void setDistanceLimit(double limit){
        for(int i=0;i<path.length-1;i++){
            for(int j=i+1;j<path[i].length;j++){
                if(path[i][j]>limit){
                    path[i][j]=Double.POSITIVE_INFINITY;
                    path[j][i]=path[i][j];
                }
            }
        }
    }

    public void shortestPath(int start){
        weight=new double[path.length];
        boolean []found=new boolean[path.length];

        parent=new int[path.length];

        for(int i=0;i<path.length;i++){
            weight[i]=path[start][i];
            found[i]=false;
            parent[i]=start;
        }

        weight[start]=0;
        found[start]=true;

        for(int i=0;i<path.length;i++){

            int minId=0;
            double minValue=Double.MAX_VALUE;
            for(int j=0;j<path.length;j++){
                if(!found[j])
                    if(minValue>weight[j]){
                        minValue=weight[j];
                        minId=j;
                    }
            }

            found[minId]=true;
            for(int j=0;j<path.length;j++){
                if(!found[j])
                    if(weight[j]>minValue+path[minId][j]){
                        weight[j]=minValue+path[minId][j];
                        parent[j]=minId;
                    }
            }
        }

    }


    public static void main(String []args){
        double [][]path={{0,10,20},{20,0,7},{8,9,0}};
        Graph g=new Graph(path);
        g.setDistanceLimit(15);

        int start=0;
        int goal=path.length-1;
        g.shortestPath(start);
        System.out.printf("The shortest distance between %d to %d is %.2f\n",start,goal,g.getShortestDistanceTo(goal));

        Object []pathList=g.getPathTo(goal);
        System.out.printf("Path from %d to %d is ",start,goal);
        for(int i=0;i<pathList.length;i++)
            System.out.printf("-> %s ",pathList[i].toString());
    }
}