Question
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
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
---------------------------------------------------------------------------------------------------------------------------------------------------
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
mGraph.add(i, new LinkedList
System.out.println ("From -> " + fromVertex + " to " + toVertex + " Dist " + distance); LinkedList
// Process the line of text
void PrintGraph () { // Go through the Adjacency Matrix
for (int vert = 1; vert <= mGraph.size(); vert++) { LinkedList
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