Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

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

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Database Horse Betting The Road To Absolute Horse Racing 2

Authors: NAKAGAWA,YUKIO

1st Edition

B0CFZN219G, 979-8856410593

More Books

Students also viewed these Databases questions