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

	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 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 double shortestPath(int start,int goal){
		double []weight=new double[path.length];
		boolean []found=new boolean[path.length];

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

		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];
					}
			}
		}

		return weight[goal];
	}

	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;
		System.out.printf("The shortest distance between %d to %d is %.2f ",start,goal,g.shortestPath(start,goal));
	}
}