Use Dijkstra's algorithm with the provided graph class to find the shortest distance between 2 vertices:

I have a class that creates a graph using the rome99 dataset. The Graph class constructor takes a filename as a parameter (in this case the Rome99 dataset which includes all the roads in Rome with streets as edges) and creates the graph data structure based on the Rome99.gr file. I need to create a Paths class which, conceptually, the path stores information on each vertexs distance from the start vertex, as well as best previous-vertex to reach a given vertex.

Paths paths = new Paths(graph, startVertex);

The Paths class maintains a priority queue of all vertices sorted by the distance from the startVertex. The member function getNextVertex() returns the next vertex from the priority queue because thats the next closest vertex which will be used for relaxation next. The next step is performed by the member function:

paths.applyRelaxation(w);

After all the vertices are thus processed, the function :

printShortestPath (endVertex);

Is used for printing the path from the startVertex to a specified endVertex passed as the parameter to the function. Note that after the relaxation step is complete the paths object has the shortest paths for all vertices starting from the chosen startVertex.

I will provide the graph class below if someone could provide their implementation of how the Paths class might be implemented. Any input or suggestions here would be much appreciated. Java is the source language but any language representation will work. Thanks!!

Graph class:

public class Graph { 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(); } }