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; int mEdgeCount;

Vector> getGraph() {return mGraph;} LinkedList getAdj(Integer vertex) { return mGraph.get(vertex.intValue()); } Integer getVertexCount() {return mVertexCount;}

// 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>(mVertexCount+1);

for (int i = 0; i

System.out.println (i); mGraph.add(i, new LinkedList()); } System.out.println ("Size of Vector = " + mGraph.size()); inFile.nextLine(); } else if (tok.equals("a")) { Integer fromVertex = inFile.nextInt(); Integer toVertex = inFile.nextInt(); Integer distance = inFile.nextInt(); Vertex v = new Vertex(); v.mVertId = toVertex; v.mDistance = distance;

//System.out.println ("From -> " + fromVertex + " to " + toVertex + " Dist " + distance); LinkedList adj = mGraph.get(fromVertex); adj.add(v); inFile.nextLine(); } else { System.out.println ("Found an illegal code: " + tok); } } } catch (Exception e) { System.out.println ("Caught Exception " + e.getMessage()); } }

// 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 vertEnum = adj.iterator(); vertEnum.hasNext();) { Vertex toVert = vertEnum.next(); System.out.print (" " + toVert.mVertId + " (" + toVert.mDistance + ") "); } System.out.println(); } } }

-------

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)