Q: You are given a file called \"citypairs.txt\" (attached to this assignment) w
ID: 666767 • Letter: Q
Question
Q:
You are given a file called "citypairs.txt" (attached to this assignment) which contains pairs of cities and the distances between them. Each city that appears in the file is a node of the graph. Each pair of cities represents an edge. The weight of each edge is the distance between those cities. These edges are undirected that is if a pair exists in the file, you can go between those two cities in either direction. Your program should take, as a command line argument, the name of the file with the city pairs.
Your program should take in the name of this file as a command line argument and should then build up an internal representation of the graph. Since we are ultimately going to implement Dijkstra's algorithm which expects a directed graph, and since the graph above is undirected, you should put two edges in for each edge in the file: one from city A to city B, and one going city B to city A. The program should then print out a list of all cities and prompt the user to enter one of the city names.
Your program will then implement Dijkstra's algorithm (using a priority queue) on this graph using the user specified city as a starting point. It should print out the shortest path from the starting city to each city in graph. Show all cities along the path in order. It should also print out the total length of each path.
Also: the priority queue used should be (mainly) Weiss' BinaryHeap (http://users.cis.fiu.edu/~weiss/dsaajava3/code/BinaryHeap.java) and the citypairs.txt can be found below.
Explanation / Answer
package com.tutai;
import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
class Vertex implements Comparable<Vertex>
{
public final String name; //name of the vertex
public Edge[] adjacencies; //to store adjacent paths of a vertex
public double minDistance = Double.POSITIVE_INFINITY;
public Vertex previous; //previous vertex
public Vertex(String argName) { name = argName; } //parameterized constructor
public String toString() { return name; } //return name of the vertex
public int compareTo(Vertex other)
{
return Double.compare(minDistance, other.minDistance); //compare the minimum distance
}
}
class Edge
{
public final Vertex target; //target vertex
public final double weight; //vertex weight
public Edge(Vertex argTarget, double argWeight) //parameterized constructor
{ target = argTarget; weight = argWeight; }
}
public class Dijkstra
{ /*method to compute the path between vertices*/
public static void computePaths(Vertex source)
{
source.minDistance = 0.0; //initialize minimum distance to 0.0
PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>(); //to maintain a queue of vertices
vertexQueue.add(source); //add source to the vertex queue
while (!vertexQueue.isEmpty()) {
Vertex u = vertexQueue.poll();
for (Edge e : u.adjacencies) //loop through each edge
{
Vertex v = e.target;
double weight = e.weight;
double distanceThroughU = u.minDistance + weight;
if (distanceThroughU < v.minDistance) {
vertexQueue.remove(v);
v.minDistance = distanceThroughU ;
v.previous = u;
vertexQueue.add(v);
}
}
}
}
/*method to compute the shortest path*/
public static List<Vertex> getShortestPathTo(Vertex target)
{
List<Vertex> path = new ArrayList<Vertex>();
for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
path.add(vertex);
Collections.reverse(path);
return path;
}
public static void main(String[] args)
{
/*create and initialize vertices*/
Vertex Albuquerque = new Vertex("Albuquerque");
Vertex Atlanta = new Vertex("Atlanta");
Vertex Boston=new Vertex("Boston");
Vertex Chicago = new Vertex("Chicago");
Vertex Dallas = new Vertex("Dallas");
Vertex Denver = new Vertex("Denver");
Vertex LasVegas=new Vertex("LasVegas");
Vertex LosAngeles=new Vertex("LosAngeles");
Vertex Memphis=new Vertex("Memphis");
Vertex Miami=new Vertex("Miami");
Vertex NewOrleans=new Vertex("NewOrleans");
Vertex NewYork=new Vertex("NewYork");
Vertex Omaha=new Vertex("Omaha");
Vertex Peoria=new Vertex("Peoria");
Vertex Phoenix=new Vertex("Phoenix");
Vertex Pittsburgh=new Vertex("Pittsburgh");
Vertex SanFrancisco=new Vertex("SanFrancisco");
Vertex SaltLake=new Vertex("SaltLake");
Vertex StLouis=new Vertex("St.Louis");
Vertex Tulsa=new Vertex("Tulsa");
Vertex Washington=new Vertex("Washington");
/*assign the adjacent edges to each vertex*/
Albuquerque.adjacencies = new Edge[]{ new Edge(LasVegas, 466.4386348),
new Edge(Tulsa, 636.2554518)};
Atlanta.adjacencies = new Edge[]{ new Edge(Memphis, 317.3168763),
new Edge(Washington, 529.9226359) };
Chicago.adjacencies = new Edge[]{ new Edge(Boston, 806.7961329)};
Dallas.adjacencies = new Edge[]{ new Edge(Tulsa, 301.7614952),
new Edge(Memphis, 403.9764845),
new Edge(Albuquerque,562.8578861),
new Edge(Atlanta, 685.5603547)};
Denver.adjacencies = new Edge[]{ new Edge(SaltLake, 359.5677961),
new Edge(Omaha, 452.4919889)};
LasVegas.adjacencies = new Edge[]{ new Edge(SaltLake, 359.6804137),
new Edge(SanFrancisco, 392.2307994),
new Edge(Denver,589.688901)};
LosAngeles.adjacencies = new Edge[]{ new Edge(LasVegas, 224.5083517),
new Edge(SanFrancisco, 331.1268639)};
Memphis.adjacencies = new Edge[]{ new Edge(StLouis, 245.7173173),
new Edge(Tulsa, 287.1671987)};
Miami.adjacencies = new Edge[]{ new Edge(Atlanta, 604.2151935),
new Edge(NewOrleans, 648.2969998)};
NewOrleans.adjacencies = new Edge[]{ new Edge(Atlanta, 402.3443799),
new Edge(Dallas, 431.0197211)};
NewYork.adjacencies = new Edge[]{ new Edge(Boston, 183.4393633)};
Omaha.adjacencies = new Edge[]{ new Edge(Chicago, 410.1219331)};
Peoria.adjacencies = new Edge[]{ new Edge(Chicago, 117.4563749),
new Edge(Omaha, 327.2002445)};
Phoenix.adjacencies = new Edge[]{ new Edge(Albuquerque, 316.7412193),
new Edge(LosAngeles, 350.382648)};
Pittsburgh.adjacencies = new Edge[]{ new Edge(NewYork, 315.9129627),
new Edge(Chicago, 384.7037821)};
SanFrancisco.adjacencies = new Edge[]{ new Edge(SaltLake, 570.6356105)};
StLouis.adjacencies = new Edge[]{ new Edge(Peoria, 148.2767682),
new Edge(Washington, 676.0096153)};
Tulsa.adjacencies = new Edge[]{ new Edge(StLouis, 269.0464644),
new Edge(Denver, 551.6420941)};
Washington.adjacencies = new Edge[]{ new Edge(Pittsburgh, 185.3483207),
new Edge(NewYork, 197.0913494)};
SaltLake.adjacencies = new Edge[]{new Edge(SanFrancisco,570.6356105)};
Boston.adjacencies = new Edge[]{new Edge(NewYork,183.4393633)};
Vertex[] vertices = {Albuquerque,Atlanta,Boston,Chicago,Dallas,Denver,LasVegas,LosAngeles,Memphis,Miami,NewOrleans,NewYork,Omaha,Peoria,Phoenix,Pittsburgh,SanFrancisco,SaltLake,StLouis,Tulsa,Washington};
Scanner s=new Scanner(System.in);
System.out.println("Enter staring city:");
String city=s.next();// get the user specified starting city
Vertex vcity=null;
switch(city){
case "Albuquerque":
vcity=Albuquerque;
break;
case "Atlanta":
vcity=Atlanta;
break;
case "Boston":
vcity=Boston;
break;
case "Chicago":
vcity=Chicago;
break;
case "Dallas":
vcity=Dallas;
break;
case "Denver":
vcity=Denver;
break;
case "LasVegas":
vcity=LasVegas;
break;
case "LosAngeles":
vcity=LosAngeles;
break;
case "Memphis":
vcity=Memphis;
break;
case "Miami":
vcity=Miami;
break;
case "NewOrleans":
vcity=NewOrleans;
break;
case "NewYork":
vcity=NewYork;
break;
case "Omaha":
vcity=Omaha;
break;
case "Peoria":
vcity=Peoria;
break;
case "Phoenix":
vcity=Phoenix;
break;
case "Pittsburgh":
vcity=Pittsburgh;
break;
case "SanFrancisco":
vcity=SanFrancisco;
break;
case "SaltLake":
vcity=SaltLake;
break;
case "StLouis":
vcity=StLouis;
break;
case "Tulsa":
vcity=Tulsa;
break;
case "Washington":
vcity=Washington;
break;
}
computePaths(vcity); //compute each path from vertex a
for (Vertex v : vertices) //iterate through each vertex
{
System.out.println("Distance to " + v + ": " + v.minDistance);
List<Vertex> path = getShortestPathTo(v); //compute the shortest path from vertex a to each vertex
System.out.println("Path: " + path); //display the shortest path
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.