public class FibonacciSSP {
	//Fibonacci Heap Schema
	final int MAX=5000;
    public int n;
    public int length[][]; 
    private int dist[];
    private boolean s[];
    private PointerToHeap[] Pointer; 
    
    public FibonacciSSP (AdjGraph G,int nn){
    	n=nn;
    	length=new int [n][n];
        for (int i=0;i<n;i++)
        	for (int j=0;j<n;j++){
        		length[i][j]=G.getWeight(i,j);
        	}
       dist=new int[n];
       s=new boolean[n];
	}
    
    public int[] FShortestPath(int v){
    //find the shortest path	
    	Pointer = new PointerToHeap[n];
    	for (int i=0;i<=n-1;i++){
    		Pointer [i] =new PointerToHeap();
    	}
    	
      	for(int i=0;i<=n-1;i++){
			Pointer[i].setDist(MAX);
			s[i]=false;
		}
    	    Pointer[v].setDist(0);;
            dist[v]=0;
            s[v]=true;
            Pointer[v].setPointer(new FibonacciNode(Pointer[v].getDist(), v)); 
            FibonacciHeap p=new FibonacciHeap();
            //insert the source node into the Fibonacci Heap
            p.Insert((FibonacciNode)Pointer[v].getPointer());
            while(p.isEmpty()== true){

            	FibonacciNode temp= p.DeleteMin();
            	//call deleteMin() to return the minimum node in graph
            	    int u= temp.count;
            	    // u is the number of the minimum node
            	    s[u]=true;
                    for(int w=0;w<=n-1;w++){
                    	if(!this.s[w]){
                             if(Pointer[u].getDist()+length[u][w]<Pointer[w].getDist()){
                            	 // if the current cost is less than history
                                  Pointer[w].setDist(Pointer[u].getDist()+length[u][w]); 
                                  //update in Ponter []
                                     if(Pointer[w].getPointer()!=null){
                                      // has existed in heap               
                                    	p.DecreaseKey((FibonacciNode)Pointer[w].getPointer(), length[u][w]);
                                      }else// not in heap
                                      {                                    	
                                       //insert the node to the heap
                                       Pointer[w].setPointer(new FibonacciNode(Pointer[w].getDist(), w)); 
                                       p.Insert((FibonacciNode)Pointer[w].getPointer());
                                      }
                            }
                    	}           
                    }
            }
            for(int i=0;i<=n-1;i++){
    			dist[i]=Pointer[i].getDist();  
    			// save the shortest path in the dist[] array
            }
            return dist;
    }
    

}