This is assignment to be done all in Java In this project, you will code the Dij
ID: 3737856 • Letter: T
Question
This is assignment to be done all in Java
In this project, you will code the Dijsktra algorithm, as it was discussed in class. The algorithm will be used to calculate the distance between 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 Hawaii excluded) 1-Input Data representing the distances between all the capitals will be stored in an adjacency matrix. Since there is 48 The data states in the contingent Unites States, the matrix wil be a 48x48 matrix: int distanceMatrix[ 481[48 For example, distanceMatrix] will be the distance between the capitals of state 0 and state 1. (of course this will be exactly as distance[1]0. 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 itself to be 0 Actual values are given at section "data values", at the end of this document. 2-Data Representation You will use Dijkstra's algorithm to calculate the shortest path from the capital of state 0 to all other capitals To map the tracing 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 right) v known d, P, class vertex public boolean known; public int distance; public int previousVertex // the Pv column // the known column // the d, column 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: vertex vertexArrayl7; V7 To represent infinity, we will use a big int value (like 9999). An example initial value of the second vertex, matching the example table on the right will be: vertexArray[ 1.known-false; vertexArray[11.distance-999p; vertexArray[ 11 previousVertex-0; for the state capital problem we are solving in this problem, you will use a vertex array of 48 elementsExplanation / Answer
ShortestPath.java
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 ShortestPath {
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 )
{
}
}
}
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
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.