Question
Use Java import java.util.*; import java.io.*; import java.lang.reflect.Array; public class Graph { public class Vertex{ Integer mVertId; Integer mDistance; } Vector > mGraph; int mVertexCount;
Use Java
import java.util.*; import java.io.*;
import java.lang.reflect.Array;
public class Graph {
public class Vertex{ Integer mVertId; Integer mDistance; }
Vector
Vector
// Constructor that uses an adjacency specified as a GR file
public Graph (String fileName) { try{ Scanner inFile = new Scanner(new FileReader(fileName)); while (inFile.hasNextLine()) { String tok = inFile.next(); tok.trim();
if (tok.equals("c")) { inFile.nextLine(); }
else if (tok.equals("p")) { String code = inFile.next(); mVertexCount = inFile.nextInt(); mEdgeCount = inFile.nextInt(); System.out.println ("Vertex Count " + mVertexCount); mGraph = new Vector
for (int i = 0; i
System.out.println (i); mGraph.add(i, new LinkedList
//System.out.println ("From -> " + fromVertex + " to " + toVertex + " Dist " + distance); LinkedList
// Print Graph - Utility Function
void PrintGraph () { // Go through the Adjacency Matrix
for (int vert = 1; vert adj = mGraph.get(vert); System.out.print ("From Vertex: " + vert); for (Iterator
-------
public class Main { public static void main(String[] args) { String grFile = args[0]; Integer startVertex = Integer.parseInt(args[1]); Integer endVertex = Integer.parseInt(args[2]); // Create Graph Object Graph graph = new Graph(grFile); Paths paths = new Paths(graph, startVertex); // Go through the relaxation process taking closest vertex from PQ Integer w; while ((w = paths.getNextVertex()) != null) { paths.applyRelaxation(w); } // Print the shortest path paths.printShortestPath (endVertex); } }
You are to implement Dijkstra's Algorithm for finding an optimal path between vertices of a graph. Specifically, your main program will take in three parameters: 1. 2. 3. Name a graph file Starting Vertex Ending Vertex It will produce an output that - (a) Lists the length of the path between the starting and the ending vertex b) Traversal Information of the path from start to end vertex as shown in the sample output below Graph representation is described on the DIMACS website: http://www.dis.uniroma1.it/challenge9/download.shtml Your program will be tested on the graph Rome99 dataset - which is a large portion of the directed road network of the city of Rome, Italy (1999) containing 3353 vertices and 8870 edges: http://www.dis.uniroma1.it/challenge9/data/rome/rome99.gr Shown below is the main program illustrating the manner in which your class will be instantiated and the functions are called: public class Main t public static void main (String[] args) string grFile=args[0]; Integer startvertex = Integer.parseln t (args [1]); Integer endvertexInteger.parseInt (args [2])i // Create Graph Object Graph graphnew Graph (grFile) Paths paths= new Paths (graph, startvertex); 7 Go through the relaxation process taking closest vertex from P Integer w while ( (w = paths. getNextVertex()) != null) paths.applyRelaxation (w) // Print the shortest path paths printShortestPath (endvertex) You are to implement Dijkstra's Algorithm for finding an optimal path between vertices of a graph. Specifically, your main program will take in three parameters: 1. 2. 3. Name a graph file Starting Vertex Ending Vertex It will produce an output that - (a) Lists the length of the path between the starting and the ending vertex b) Traversal Information of the path from start to end vertex as shown in the sample output below Graph representation is described on the DIMACS website: http://www.dis.uniroma1.it/challenge9/download.shtml Your program will be tested on the graph Rome99 dataset - which is a large portion of the directed road network of the city of Rome, Italy (1999) containing 3353 vertices and 8870 edges: http://www.dis.uniroma1.it/challenge9/data/rome/rome99.gr Shown below is the main program illustrating the manner in which your class will be instantiated and the functions are called: public class Main t public static void main (String[] args) string grFile=args[0]; Integer startvertex = Integer.parseln t (args [1]); Integer endvertexInteger.parseInt (args [2])i // Create Graph Object Graph graphnew Graph (grFile) Paths paths= new Paths (graph, startvertex); 7 Go through the relaxation process taking closest vertex from P Integer w while ( (w = paths. getNextVertex()) != null) paths.applyRelaxation (w) // Print the shortest path paths printShortestPath (endvertex)Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started