Using Java, you are to implement Dijkstras Algorithm for finding an optimal path between vertices of a graph. Specifically, your main program will take in three parameters: 1. Name a graph file 2. Starting Vertex 3. 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

Sample input and outputs:

Main rome99.gr 1 10 Output: 1 --> 22 --> 21 --> 17 --> 18 --> 19 --> 15 --> 20 --> 160 --> 159 --> 9 --> 10 Shortest path from 1 to 10 is 8935.0 units

Main rome99.gr 100 300 Output: 100 --> 96 --> 97 --> 99 --> 103 --> 104 --> 106 --> 110 --> 200 --> 202 --> 201 --> 230 --> 238 --> 208 --> 241 --> 265 --> 273 --> 285 --> 300 Shortest path from 100 to 300 is 17266.0 units

Shown below is the main and Graph.java . Make the Paths.java file to work with the main and Graph.java . Graph.java can be modified if necessary.

---------------------------------------------------------------------------------------------------------------------------------------------------

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); } }

-------------------------------------------------------------------------------------------------------------------------

import java.util.*; import java.io.*;

import java.lang.reflect.Array;

/** * Parser for .gr files. Creates an Adjacency List. */

public class Graph {

private class Vertex{ Integer mVertId; Integer mDistance; }

Vector> mGraph; int mVertexCount; int mEdgeCount;

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

//System.out.println ("Token found = '" + tok + "'");

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 <= mVertexCount; 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()); } }

// Process the line of text

void PrintGraph () { // Go through the Adjacency Matrix

for (int vert = 1; vert <= mGraph.size(); vert++) { LinkedList 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(); } } }