The following is to be done in Java Problem (100 points) In this projcct,u will

Question

The following is to be done in Java

Problem (100 points) In this projcct,u will code the Dijsktra algorithm, as it was discussed in class. The algorithm will be uscd to cakculate the distance berween the capital of the first US state (we call it state 0), and the capitals of the rest of the 48 states forming the contingent United States. (Alaska and I lawaii excluded) 1-Input Data representing the distances between all the ca pitals will be stoned in an adjacency matrix. Since there is 48 The data states in the contingent Unites States, the matris will be a 48x48 matrix: int distanceMatrix(48 148] For cxample, distanccMatrx1 will be the distance betwcen the capitals of state 0 and state 1. (of course this will be exactly as distanceOD.Your code will initialize the matrix variable in the beginning of the program, using the data at the end of this project. Naturally, the distance between each capital and it self to be 0. Actual values are given at section "data vaues'", at the end of ts document. 2-Data Representation You will use Dzjkstra's algorithm to calculate the shortest path trom the capital of state {) to all other capitals. To map the racing table used in class while trace the progress of Dijkstra's algorithm, you will use the following vertex class (matching the tracing table on the righty: known p? class vertex public boolean known; public int distance; public int previousvertex; / the P. column the known column / the d, columrn and you will create an array of vertex. In order to match the class example, you will need a matrix of 7 vertexes, such as: oc 0 vertex vertexArray To represenl inlinty, we will use abg nL value (i e 9999). An exarnple nual value o[the second vertes, maching the example table on the right will he vertexArray1. known false ver texArrayt1.distance 999p; vertexArray1] previousvertex 0 for the state capital problem we are solving in this problem, you will use a vertex array of 48 elements

Explanation / Answer

import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;

public class ShortestPath1 {
  
    int distanceMatrix[][] ;
    vertex vertexArray[] ;
    class vertex {
        public boolean known; // the known column
        public int distance; // the dv column
        public int previousVertex; // the pv column
    }
  
    void acceptDistanceMatrixData(String file) throws FileNotFoundException{
      
      
        FileInputStream fstream = new FileInputStream(file);
        DataInputStream in = new DataInputStream(fstream);
     
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(in))) {
            String line = null;
          
            while ((line = reader.readLine()) != null) {
              
                System.out.println(line);
              
                intitializeDistanceMatrix( line ) ;
            }
        }
        catch (IOException x) {
            System.err.format("IOException: %s%n", x);
        }  
      
    }
      
  
     void intitializeDistanceMatrix(String line){
       
         if ( line != null ){
          
           String[] intsToParse = line.split(" ");
           int[] info = new int[intsToParse.length];
           // Now just parse each part in turn
            for (int i = 0; i < info.length; i++)
            {
                info[i] = Integer.parseInt(intsToParse[i]);
            }
            distanceMatrix[info[0]][info[1]] = info[2] ;
        }
      
    }
   
   
     void initializeVertexArray(){
        vertexArray[0] = new vertex() ;
        vertexArray[0].known = false ;
        vertexArray[0].distance = 0 ;
        vertexArray[0].previousVertex = 0 ;
       
        for( int i = 1 ; i <48 ; i++){
            vertexArray[i] = new vertex() ;
            vertexArray[i].known = false ;
            vertexArray[i].distance = 9999 ;
            vertexArray[i].previousVertex = 0 ;
         }
       
       
     }

     void dijkstraAlgorithm( ){
      
         initializeVertexArray() ;
         int k =0 ;
         while( !(vertexArray[k].known)){
           
             vertex v = vertexArray[k] ;
           
             for(int i = 0 ; i < 48 ; i++)
                 for( int j= 0 ; j< 48 ; j++ )
                     if( distanceMatrix[i][j] != 0 )
                     {
                       
                     }
                       
             
        }
         //need to complete the algortihm
       
     }
   
     void printShortestDistances(){
       
        for (int i=0 ; i<48 ; i++){
            System.out.println( "The shortest distance between state[0] and state[" +i+ "] is: " + vertexArray[i].distance);
        }
       
       
       
     }
   
    public static void main(String[] args) throws FileNotFoundException{
     
        ShortestPath s = new ShortestPath() ;
        String filepath = "datavalues.txt" ;
        s.acceptDistanceMatrixData(filepath) ;
        s.dijkstraAlgorithm() ;
        s.printShortestDistances() ;
      
    }
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.