COP 3530
  Section U03
  Spring 2017


                      A PROGRAM FOR HW #4
                      ===================


  I. The Program:
  ---------------


  public class Hw4
  {
   
    public static void main(String[] args) {
        // print title
        System.out.println("TESTING THE SHORTEST PATHS ALGORITHM");
        System.out.println("====================================\n\n\n");
        
         // define the adjacency lists
        LinkedList<Data>[] weight = new LinkedList[NO_OF_NODES];
        for (int i = 0; i < NO_OF_NODES; i++)
            weight[i] = new LinkedList<Data>();
        
        weight[0].add(new Data(5,20));
        weight[1].add(new Data(3,35));
        weight[1].add(new Data(5,80));
        weight[1].add(new Data(2,10));
        weight[2].add(new Data(4,15));
        weight[2].add(new Data(0,50));
        weight[2].add(new Data(3,20));
        weight[3].add(new Data(5,45));
        weight[3].add(new Data(2,15));
        weight[4].add(new Data(5,25));
        weight[4].add(new Data(0,20));
        weight[5].add(new Data(3,25));
        weight[6].add(new Data(4,10));
        weight[6].add(new Data(5,20));
        
  
        System.out.println("The graph is:");
        printLists(weight);
   
        
        // find the shortest distance
        int[] d = new int[NO_OF_NODES];
        d = shortestPaths(1,weight);
        
        // print the shortest path
        System.out.println("\nThe shortest paths from 1 to the other vertices"
            + " is: ");
        for (int i = 0; i < NO_OF_NODES; i++)
            if ( d[i] < INFINITY)
                System.out.println("d[1," + i + "] = " + d[i]);
            else
                System.out.println("d[1," + i + "] = INFINITY");
        
    }
    
 
    // cost is an n X n matrix of non-negative integers
    // cost[i][j] is the cost of the arc from i to j
    // if there is no arc, the cost is INFINITY
    // it returns the cost of the minimal path from
    // the vertex v to the vertices of the graph
    public static int[] shortestPaths( int v, LinkedList<Data>[] cost)
    {
        // get the set of vertices
        int n = cost.length;
        // declare the arrays dist and s
        // dist[i] is the distance from v to i
        // s[i] is true if there is a path from v to i
        int[] dist = new int[n];
        boolean[] s = new boolean[n];
        
        // initialialize dist
        for (int i = 0; i < n; i++)
        {
            dist[i] = INFINITY;
        }
        dist[v] = 0;
        
        ListIterator<Data> itr = cost[v].listIterator();
        while (itr.hasNext())
        {
            Data item = itr.next();
            int node = item.getVertex();
            int c = item.getCost();
            dist[node] = c;
        }   
        
        s[v] = true;
        
        // determine n-1 paths from v 
        for ( int j = 2 ; j < n  ; j++ )
        {
            // choose u such that dist[u] is minimal for all w with s[w] = false
            // and dist[u] < INFINITY
            int u = -1;
            for (int k = 0; k < n; k++)
                if ( !s[k] && dist[k] < INFINITY)
                    // check if u needs updating
                    if ( u < 0 || dist[k] < dist[u])
                        u = k;
            if (u < 0)
                break; // 
            // set s[u] to true and update the distances
            s[u]=true;
            
            // update dist[k] for s[k] = false
            itr = cost[u].listIterator();
            while (itr.hasNext())
            {
                Data item =  itr.next();
                int node = item.getVertex();
                int c = item.getCost();
                if ( !s[node] && dist[u] + c < dist[node])
                        dist[node] = dist[u] + c;
                // at this point dist[node] is the smallest cost path from
                // v to node of length j
            }    
        }     
            
        return dist;
        
    }
     
    // print the adjacency lists
    public static void printLists(LinkedList<Data>[] cost)
    {
        if (cost == null || cost.length == 0)
            System.out.println("Empty cost matrix");
        else
        {
            // print each list
            for (int i = 0; i <  cost.length; i++)
            {
                ListIterator<Data> itr = cost[i].listIterator();
                while (itr.hasNext())
                {
                    Data item =  itr.next();
                    int node = item.getVertex();
                    int c = item.getCost();
                    System.out.print(i + " ---" + c + "---> " + node + ", ");
                }
                System.out.println();
            }   
        }   
    }       
    
    
    private static final int INFINITY = Integer.MAX_VALUE;
    private static final int NO_OF_NODES = 7;

  }   

  II. The Data Class:
  -------------------

    // contains pairs vertex (an int), cost ( an int)  
    public class Data
    {
        // the fields
        private int vertex;
        private int cost;
        
        // the constructor
        public Data(int v, int price)
        {
            vertex = v;
            cost = price;
        }        
        
        // the 2 get methods
        public int getVertex()
        {
            return vertex;
        }        
        
        public int getCost()
        {
            return cost;
        }        
    }
  
  
    III. The Output:
    ----------------

    run:
    TESTING THE SHORTEST PATHS ALGORITHM
    ====================================



    The graph is:
    0 ---20---> 5, 
    1 ---35---> 3, 1 ---80---> 5, 1 ---10---> 2, 
    2 ---15---> 4, 2 ---50---> 0, 2 ---20---> 3, 
    3 ---45---> 5, 3 ---15---> 2, 
    4 ---25---> 5, 4 ---20---> 0, 
    5 ---25---> 3, 
    6 ---10---> 4, 6 ---20---> 5, 

    The shortest paths from 1 to the other vertices is: 
    d[1,0] = 45
    d[1,1] = 0
    d[1,2] = 10
    d[1,3] = 30
    d[1,4] = 25
    d[1,5] = 50
    d[1,6] = INFINITY
    BUILD SUCCESSFUL (total time: 0 seconds)