package it.cnr.iasi.giant.algorithm.distance;

// Author:	Renee L. Ramsey, W. Klostermeyer
// Algorithms: An Undergraduate Course with Programming
// Program:     dijkstra.java
// Date:	5/12/2002, 11/14/02
//
// dijkstra.java
//
// to run this program: >java dijkstra
// note the PriorityQueue class must reside in the same directory.
import java.io.IOException;	//for I/O
///////////////////////////////////////////////////////////////////////////
public class Dijkstra {
       
    /*public static void main(String[] args) throws IOException
    {
	// create a Graph object using adjacency matrix
     	GraphUtil G = new GraphUtil("graph.txt");

     	// If you want to use a Link List Graph, uncomment this out and comment
	// out the Graph object above
	// graphLinkList G = new graphLinkList("unweighted.txt","u");

	// create a randomgraph object using adjacency matrix
     	// randomgraph G = new randomgraph(20, 20, 20);


        // call dijkstra function
        dijkstra_function(G,0);


    }// end main
    */
    
//--------------------------------------------------------------

// If you want to use a Linked List Graph, 
// you must change the datatype to be graphLinkList
// If you want to use randomgraph, you must change datatype to be randomgraph
// You could probably re-write graphLinkList and randomgraph to return a Graph object,
// but I am too lazy.

   public static int[] dijkstra_function(GraphUtil G, int s) throws IOException
   {                  					// s is the index of the starting vertex
   	// declare variables
	int nVerts, u, v;
	

        nVerts = G.vertices(); 			// get number of vertices in the Graph class

        // initialize array
        int[] dist = new int[nVerts];

        for(v=0; v<nVerts; v++) 			// initializations
        {
        	dist[v] = 99999; 				// 99999 represents infinity

        }// end for

        dist[s] = 0;

        PriorityQueue Q = new PriorityQueue(dist);  		

        while(Q.Empty() == 0) 			// if heap is not empty
        {

                u = Q.Delete_root();
                v = G.nextneighbor(u);

                while(v != -1)  			// for each neighbor of u
                {
                	if(dist[v] > dist[u] + G.edgeLength(u,v)) {
                		dist[v] = dist[u] + G.edgeLength(u,v);
				Q.Update(v, dist[v]);
                         }

                	v = G.nextneighbor(u);  	// get the next neighbor of u

                }// end while

        }// end while

        return dist;
        
        /*
        System.out.println("");    			// display the array dist
        for(int row=0; row<nVerts; row++)
      	{
      		System.out.print(dist[row] + " ");
      	  	System.out.println("");
      	}// end for
        */
        
   }// end bfs_function()
   
//--------------------------------------------------------------
}///////////////////////////////////////////////////////////////////////////
