USA: +1 (725) 712-1730 
Sign in
Objective:
Work with Dijkstra's single-source shortest path algorithm.
Overview:
In this project you will use Dijkstra's algorithm to find route information
between two airports chosen by the user. The user will be shown a route that
results in the lowest price.
Details:
Write a Java program that lets the user choose two airports and finds
the route that has the least price.
Your program should read the airports.txt file that is posted, or any file
having the same format.
It should then prompt the user to enter two airports.
Dijkstra's algorithm should be run to find the cheapest route. The price,
number of connections, and actual route should be shown.
The user should be able to continue checking routes until no more routes are requested.
You are expected to write Dijkstra's algorithm yourself following the pseudocode
found in both the slides and in the textbook. You can use the Vertex class and
printPath found in the textbook if you wish.
You may not use code for Dijkstra's algorithm found from other sources.
Your output should match the sample output below:
Sample output:
Enter departure airport: DFW
Enter arrival airport: SFO
By price:
Price: 1100
Connections: 1
Route: DFW -> LAX -> SFO
Check another route (Y/N)?
AIRPORTS.TXT
ATL BOS 250 DFW 250 MOB 59
AUS DFW 59 HOU 59 SAT 59 BOS ATL 250 DFW 250 DFW ATL 250 AUS 59 BOS 250 HOU 128 LAX 1000 LIT 59 MSY 128 OKC 59 SHV 59 SFO 1200 HOU AUS 59 DFW 128 SAT 59 LAX DFW 1000 SFO 100 LIT DFW 59 MOB ATL 59 MSY DFW 128 OKC DFW 59 SAT AUS 59 HOU 59 SFO DFW 1200 LAX 100 SHV DFW 59
Expert Answer
Below is your code: –
Dijkstra.java
import java.io.File;
import java.io.FileNotFoundException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Set;
public class Dijkstra {
static HashMap<String, Vertex> mapvertex = new HashMap<String, Vertex>();
StringBuilder route = new StringBuilder();
public void dijkstra(Vertex departure, String arrival) {
Set<String> airportNames = mapvertex.keySet();
Iterator<String> airportIterator = airportNames.iterator();
while (airportIterator.hasNext()) {
Vertex vertex = mapvertex.get(airportIterator.next());
vertex.setKnown(false);
vertex.setCost(0);
vertex.setIsInfinity(true);
vertex.setPrevVertex(null);
}
departure.setIsInfinity(false);
Vertex vertex = departure;
vertex.setIsInfinity(false);
boolean arrivalFound = false;
PriorityQueue<Vertex> travvertx = new PriorityQueue<>();
for (;;) {
try {
vertex = travvertx.remove();
} catch (NoSuchElementException nsee) {
if (vertex == departure) {
} else {
break;
}
}
if (vertex == null) {
break;
}
LinkedList<AdjacentVertex> adjacentVertices = vertex.getlstadjvertx();
Iterator<AdjacentVertex> iterator = adjacentVertices.iterator();
while (iterator.hasNext()) {
AdjacentVertex adjVertex = iterator.next();
int cost = vertex.getCost() + adjVertex.getCost();
if (adjVertex.getVertex().getKnown() == false) {
if (adjVertex.getVertex().getIsInfinity()) {
adjVertex.getVertex().setCost(cost);
adjVertex.getVertex().setPrevVertex(vertex);
adjVertex.getVertex().setIsInfinity(false);
} else {
if (adjVertex.getVertex().getCost() > cost) {
adjVertex.getVertex().setCost(cost);
adjVertex.getVertex().setPrevVertex(vertex);
}
}
if (!travvertx.contains(adjVertex.getVertex())) {
travvertx.add(adjVertex.getVertex());
}
}
}
vertex.setKnown(true);
}
}
public int printPath(Vertex departure, Vertex arrival) {
if (arrival == departure) {
route.append(arrival.getName() + ” -> “);
return -1;
} else {
int numberOfConnections = 1 + printPath(departure, arrival.getPrevVertex());
route.append(arrival.getName() + ” -> “);
return numberOfConnections;
}
}
public static void main(String[] args) throws FileNotFoundException {
File airports = new File(“Airports.txt”);
Scanner sc1 = new Scanner(airports);
while (sc1.hasNext()) {
String airportDetail = sc1.nextLine();
String[] splitString = airportDetail.split(” “);
Vertex airport = new Vertex(splitString[0]);
mapvertex.put(splitString[0], airport);
}
sc1 = new Scanner(airports);
while (sc1.hasNext()) {
String airportDetail = sc1.nextLine();
String[] splitString = airportDetail.split(” “);
Vertex airport = mapvertex.get(splitString[0]);
LinkedList<AdjacentVertex> listadjvertx = new LinkedList<>();
for (int j = 1; j < splitString.length; j++) {
String[] subStrings = splitString[j].split(” “);
int cost = Integer.parseInt(subStrings[1]);
listadjvertx.add(new AdjacentVertex(mapvertex.get(subStrings[0]), cost));
}
airport.setadj(listadjvertx);
}
while (true) {
Dijkstra dij = new Dijkstra();
Scanner sc = new Scanner(System.in);
System.out.print(“Enter Departure Airport: “);
String departure = sc.next().toUpperCase();
System.out.print(“Enter Arrival Airport: “);
String arrival = sc.next().toUpperCase();
Vertex depvertx = mapvertex.get(departure);
Vertex arrvertx = mapvertex.get(arrival);
System.out.println(“”);
dij.dijkstra(depvertx, arrival);
System.out.println(“By Price:”);
System.out.println(“”);
int numberOfConnections = dij.printPath(depvertx, arrvertx);
System.out.println(“Price : ” + arrvertx.getCost());
System.out.println(“Connection(s): ” + numberOfConnections);
dij.route.toString();
System.out.println(“Route : ” + dij.route.substring(0, dij.route.length() – 4));
System.out.println(“”);
System.out.println(“Check Another Route? (Y/N)”);
if (sc.next().toUpperCase().equals(“N”)) {
break;
}
}
}
}
Vertex.java
import java.util.LinkedList;
public class Vertex implements Comparable<Vertex> {
private String name;
private LinkedList<AdjacentVertex> listadjvertxs;
private int cost;
private boolean known;
private boolean isInfinity;
private Vertex prevVertex;
public Vertex(String name) {
this.name = name;
this.cost = 0;
this.known = false;
this.isInfinity = true;
this.prevVertex = null;
}
public LinkedList<AdjacentVertex> getlstadjvertx() {
return this.listadjvertxs;
}
public void setadj(LinkedList<AdjacentVertex> listofadjvertx) {
this.listadjvertxs = listofadjvertx;
}
public String getName() {
return this.name;
}
public int getCost() {
return this.cost;
}
public void setCost(int cost) {
this.cost = cost;
}
public boolean getKnown() {
return this.known;
}
public void setKnown(boolean known) {
this.known = known;
}
public boolean getIsInfinity() {
return this.isInfinity;
}
public void setIsInfinity(boolean isInfinity) {
this.isInfinity = isInfinity;
}
public Vertex getPrevVertex() {
return this.prevVertex;
}
public void setPrevVertex(Vertex prevVertex) {
this.prevVertex = prevVertex;
}
public int compareTo(Vertex vertex) {
return this.cost – vertex.getCost();
}
public String toString() {
return this.name;
}
}
AdjacentVertex.java
public class AdjacentVertex {
private Vertex vertex;
private int cost;
public AdjacentVertex(Vertex vertex, int cost) {
this.vertex = vertex;
this.cost = cost;
}
public Vertex getVertex() {
return this.vertex;
}
public void setVertex(Vertex vertex) {
this.vertex = vertex;
}
public int getCost() {
return this.cost;
}
public void setCost(int cost) {
this.cost = cost;
}
}
Sample Output: –
Enter Departure Airport: DFW
Enter Arrival Airport: SFO
By Price:
Price : 1100
Connection(s): 1
Route : DFW -> LAX -> SFO
Check Another Route? (Y/N)
Y
Enter Departure Airport: ATL
Enter Arrival Airport: AUS
By Price:
Price : 309
Connection(s): 1
Route : ATL -> DFW -> AUS
Check Another Route? (Y/N)
Y
Enter Departure Airport: MOB
Enter Arrival Airport: DFW
By Price:
Price : 309
Connection(s): 1
Route : MOB -> ATL -> DFW
Check Another Route? (Y/N)
N
