//This code implements Dijkstra's algorithm for the 
//single-source, shortest-paths problem.
//It uses the Heap implementation defined earlier.
//Since that heap returns max values and we want min values,
//we negate priorities before inserting into heap.
//The code assumes that the graph is passed in as an incidence
//matrix. It should be made more generic...

class Dijkstra {

    //parent[i] will be parent of node i in shortest paths tree
    protected static int[] parent; 

    //minDistance[i] will be length of the shortest path from source
    //it is initialized to infinity initially in the algorithm;
    //we will use -1 to represent infinity 
    protected static int[] minDistance;

    protected static boolean isLifted(int i) {
	return (minDistance[i] != -1);
    }
	  
    //G is incidence matrix of graph, r is the source node
    //If I had time, I'd make this more generic by defining a IGraph interface
    //and permitting the parameter to be any implementation of this interface    
    public static void shortestPaths(int[][] G, int r) {
        parent = new int[G.length]; 
        minDistance = new int[G.length];//length of shortest path from r
        //our heap returns max element but we want min, 
        //so we'll negate all priorities 
        Heap h = new Heap();

        //initialize minDistance to infinity (we'll use -1)
	for (int i = 0; i < G.length; i++) 
	    minDistance[i] = -1;
	//insert source node in priority queue using a dummy start node -1
        PQElement pe = new PQElement(new Edge(-1,r), 0);
        h.put(pe);
        System.out.println("Inserted into heap:" + pe);

	int counter = 1; //counts number of times gets are done from heap
	while (! h.isEmpty()) {	    
            
	    pe = (PQElement)(h.get());
	    System.out.println("Extracted from heap:" + pe);
	    Edge b = (Edge)(pe.getObject());
	    int qNode = b.dest(); //the node in question

	    //check if qNode is already a tree node
	    if (isLifted(qNode)) continue;

	    //qNode is a frontier node, and we've found shortest path to it
	    int tNode = b.source(); //the tree node that's source of b
	    int l = - pe.getPriority();
	    parent[qNode] = tNode;
	    minDistance[qNode] = l;

	    //loop over all neighbors of qNode to find new bridges
	    for (int i = 0; i < G.length; i++)
		//if there is edge qNode->i and i is not a tree node
		if ((G[qNode][i] != 0) && (! isLifted(i))) {
		    pe = new PQElement(new Edge(qNode,i), -(l + G[qNode][i]));
                    h.put(pe);
		    System.out.println("Inserted into heap:" + pe);
		    counter++;
		}
	}
        System.out.print("Parent nodes in shortest-distance tree:");
	printArray(parent);
        System.out.print("Shortest distances from start node:");
	printArray(minDistance);
	System.out.println("Number of heap insertions:" + counter);
    }

  public static void printArray(int[] foo) {
    for (int i = 0; i < foo.length; i++) 
      System.out.print (foo[i] + " ");
    System.out.println();
  }

  public static void main(String[] args) {
      //This is the graph in the lecture notes
      int[][] G = new int[9][9];
      G[0][1] = 2;
      G[1][0] = 2;
      G[0][6] = 5;
      G[6][0] = 5;
      G[0][5] = 9;
      G[5][0] = 9;
      G[1][2] = 4;
      G[2][1] = 4;
      G[1][6] = 6;
      G[6][1] = 6;
      G[2][7] = 5;
      G[7][2] = 5;
      G[2][3] = 2;
      G[3][2] = 2;
      G[3][7] = 1;
      G[7][3] = 1;
      G[3][4] = 1;
      G[4][3] = 1;
      G[4][8] = 3;
      G[8][4] = 3;
      G[4][5] = 6;
      G[5][4] = 6;
      G[5][8] = 1;
      G[8][5] = 1;
      G[6][8] = 2;
      G[8][6] = 2;
      G[6][7] = 5;
      G[7][6] = 5;
      G[7][8] = 4;
      G[8][7] = 4;
      System.out.println("Starting Dijkstra .....");
      shortestPaths(G, 0);

  }

}

class Edge {
    protected int source, dest;
    
    public Edge (int s, int d) {
       source = s;
       dest = d;  
    }

    public int source() {
	return source;
    }

    public int dest() {
	return dest;
    }
    
    public String toString() {
	return "Edge:Source="+ source + " Dest=" + dest + " ";
    }
}