/***********************************
 * Dijstra's Algorithm in Java     *
 *                                 *
 * Matt Smart (mjs@cs.bham.ac.uk)  *
 * March 23, 2007                  *
 ***********************************/ 

import java.util.*;
public class Dijkstra {
    
    //define some constants
    /** "Infinity" (represented by MAX_VALUE) */
    public static final int INF=Integer.MAX_VALUE; 
    /** Number of Vertices in Graph */
    public static final int NUM_VERTICES=8;
    
    //now define the cities
    /** Constant representing Honalulu */
    public static final int HNL=0;
    /** Constant representing San Francisco */
    public static final int SFO=1;
    /** Constant representing Los Angeles */
    public static final int LAX=2;
    /** Constant representing Zorg En Hoop, Suriname */
    public static final int ORG=3;
    /** Constant representing Dallas Fort Worth */
    public static final int DFW=4;
    /** Constant representing La Guardia, New York */
    public static final int LGA=5;
    /** Constant representing T.F. Green, Providence */
    public static final int PVD=6;
    /** Constant representing Miami */
    public static final int MIA=7;
    /** Constant representing a Non-Existent airport */
    public static final int nonexistent=8;
        
    //start and end vertices
    /** The first vertex in the array */
    public static final int FIRST_VERTEX=HNL;
    /** The last vertex in the array */
    public static final int LAST_VERTEX=MIA;
    
    //list of names of cities, for output
    private String[] name={"HNL","SFO","LAX","ORD","DFW","LGA","PVD","MIA"};
    
    //now the initial distance matrix ("weight")
    private int weight[][]=
    {
      /* HNL    SFO     LAX     ORD     DFW     LGA     PVD     MIA */
        {0,     INF,    2555,   INF,    INF,    INF,    INF,    INF }, //HNL
        {INF,   0,      337,    1843,   INF,    INF,    INF,    INF }, //SFO
        {2555,  337,    0,      1743,   1233,   INF,    INF,    INF }, //LAX
        {INF,   1843,   1742,   0,      802,    INF,    849,    INF }, //ORD
        {INF,   INF,    1233,   802,    0,      1387,   INF,    1120}, //DFW
        {INF,   INF,    INF,    INF,    1387,   0,      142,    1099}, //LGA
        {INF,   INF,    INF,    849,    INF,    142,    0,      1205}, //PVD
        {INF,   INF,    INF,    INF,    1120,   1099,   1205,   0   }, //MIA
    };
    
    /*** Dijkstra's Algorithm starts here ***/
    int[] distance=new int[NUM_VERTICES];
    boolean[] tight=new boolean[NUM_VERTICES];
    int[] predecessor=new int[NUM_VERTICES];
    
	
    /**
     * Returns the Vertex (or one of the Vertices) that has minimal weight 
     * and is not already tight
     * @return Vertex with minimal weight that is non-tight
     */
    private int minimalNontight(){
        int j,u;
        
        for(j=FIRST_VERTEX; j<LAST_VERTEX; j++){
            if(!tight[j])
                break;
        }
        
        assert(j<=LAST_VERTEX);
        
        u=j; /* u is now the first vertex with nontight estimate, but maybe not the minimal one. */
        for(j++; j<=LAST_VERTEX; j++)
            if(!tight[j] && distance[j]<distance[u])
                u=j;
        
        return u;
    }
    
    /**
     * Returns the truth value of whether two nodes are neighbours (specifically in the direction
     * u to z)
     * @param u First node
     * @param z Second node
     * @return Truth value of whether "u to z" is a possible direct path.
     */
    private boolean successor(int u, int z){
        return ((weight[u][z]!=INF) && u!=z);
    }
    
    /**
     * Performs Dijkstra's algorithm on the graph, starting from the specified node. Fills distance
     * matrix with minimal total distances from start node to each other node, and fills "predecessor" matrix
     * accordingly.
     * @param s The start node
     */
    public void dijkstra(int s){
        int z,u;
        int i;
        
        distance[s]=0;
        for(z=FIRST_VERTEX; z<=LAST_VERTEX; z++){
            if(z!=s) distance[z]=INF;
            
            tight[z]=false;
            predecessor[z]=nonexistent;
        }
        
        for(i=0; i<NUM_VERTICES; i++){
            u=minimalNontight();
            tight[u]=true;
            
            for(z=FIRST_VERTEX; z<=LAST_VERTEX; z++)
                if(successor(u,z) && !tight[z] && (distance[u]+weight[u][z]<distance[z])){
                    distance[z]=distance[u]+weight[u][z]; //we've found a shortcut
                    predecessor[z]=u;
                }
        }      
    }
    
    /**
     * Runs Dijkstra's algorithm to calculate the shortest path between any start and end point, and prints that path
     * @param origin The start node
     * @param destination The end node
     */
    public void printShortestPath(int origin, int destination){
        
        assert(origin!=nonexistent && destination!=nonexistent);
        dijkstra(origin);
        
        System.out.println("The shortest path from "+name[origin]+" to "+name[destination]+" is:\n");
        
        Stack<Integer> st=new Stack<Integer>();

        for(int v=destination; v!=origin; v=predecessor[v])
            if(v==nonexistent){
                System.out.println("non-existent (because the graph is not connected).");
                return;
            }else{
                st.push(v);
            }
        
        st.push(origin);
        
        while(!st.empty())
            System.out.print(name[st.pop()]+" -> ");
        
        System.out.println("[finished]");
    }
    
    /**
     * Constructor (unused) 
     */
    public Dijkstra(){ return; }
    
    public static void main(String[] unused){
        new Dijkstra().printShortestPath(SFO, MIA);
    }
  
}