COP 3530
  Section U03
  Spring 2017



                                Hw #4
                                =====


                                                      Due date: March 22nd, 2017



     Implement the shortestPaths algorithm for the list representation 
  of graphs. In this representation, cost is an array of linked lists. 
  The list cost[i] contains all arcs that have i as source. The data field 
  of the links are pairs int, int where the first int is a vertex j and 
  the second int is the cost of the arc i -----> j.

  For example, if the arcs that start from i are the ones below,
     10        15        12
  i------>j,i------>k,i------>l   

  cost[i] is the linked list

  cost[i]-------------->|j | 10|--|------->|k | 15|--|--------->|l | 12|null|

  First you must create the data class that contains the pairs of integers, 
  a constructor, the accessor methods, and the set methods.
  Then modify the shortestPaths algorithm to have signature

  public static int[] shortestPaths( int v, LinkedList<Data>[] cost)

  The lists cost[i] are not sorted, neither by vertex, nor by cost.

  Below is a driver for this your assignment.



                       DRIVER FOR THE OPTIONAL HOMEWORK
                       ================================



  import java.util.LinkedList;
  import java.util.ListIterator;

  public class Main 
  {
    
     public static void main(String[] args) 
     {
     
        // print title
        System.out.println("TESTING THE SHORTEST PATHS ALGORITHM");
        System.out.println("====================================\n\n\n");
       
        // define a cost matrix
        LinkedList<Data>[] weight = new LinkedList[6];
        for (int i = 0; i < 6; i++)
            weight[i] = new LinkedList<Data>();
        weight[0].add(new Data(1,50));
        weight[0].add(new Data(2,10));
        weight[0].add(new Data(4,45)); 
        weight[1].add(new Data(4,10));
        weight[1].add(new Data(2,15));
        weight[2].add(new Data(0,20));
        weight[2].add(new Data(3,15));
        weight[3].add(new Data(4,35));
        weight[3].add(new Data(1,20));
        weight[4].add(new Data(3,30));
        weight[5].add(new Data(3,3));
        int[] d = new int[6];
        d = shortestPaths(0,weight);
        System.out.println("\nThe shortest paths from 0 to the other vertices is: ");
        for (int i = 0; i < 6; i++)
            if ( d[i] < INFINITY)
                System.out.println("d[0," + i + "] = " + d[i]);
            else
                System.out.println("d[0," + i + "] = INFINITY");
        
        System.out.println("\nThe shortest paths from 5 to the other vertices is: ");
        d = shortestPaths(5,weight);
        for (int i = 0; i < 6; i++)
            if ( d[i] < INFINITY)
                System.out.println("d[5," + i + "] = " + d[i]);
            else
                System.out.println("d[5," + i + "] = INFINITY");
        
     }
    
    
    
     // you write it
     public static int[] shortestPaths( int v, LinkedList[] cost)
     {
        
     }
    
     // the constant
     private static final int INFINITY = Integer.MAX_VALUE;
  }

  You should also write the class

  public class Data

  on a separate Java file. The class must have two private fields, the vertex and the cost.
  You can make the cost integer or real. It has a public constructor that takes as input 
  the vertex and the cost, in this order and the public mehods getVertex and getCost that 
  return the fields.
  You may want to add the set methods, but this is optional.


  The output:




  TESTING THE SHORTEST PATHS ALGORITHM
  ====================================




  The shortest paths from 0 to the other vertices is: 
  d[0,0] = 0
  d[0,1] = 45
  d[0,2] = 10
  d[0,3] = 25
  d[0,4] = 45
  d[0,5] = INFINITY

  The shortest paths from 5 to the other vertices is: 
  d[5,0] = 58
  d[5,1] = 23
  d[5,2] = 38
  d[5,3] = 3
  d[5,4] = 33
  d[5,5] = 0