I am trying to make a program that will have a list of cities and travel times between the cities. In the program I have to ask the user for a starting location and a destination. The program will then use the information from the user input to calculate the shortest path between the start and destination.
I don't know what to do to let the program accept the user input as a Vertex so that I can use the input to plug it into
computePaths(VERTEX_START_INPUT_HERE);
System.out.println("\nDistance to " + VERTEX_DESTINATION_INPUT_HERE + ": " + v1.minDistance);
List path = getShortestPathTo(VERTEX_DESTINATION_INPUT_HERE);
Here's the preview of the code that I'm having trouble in:
System.out.println("List of Cities:");
for (Vertex v : vertices)
{
System.out.println(v);
}
Scanner k = new Scanner(System.in);
System.out.println("\nEnter start location: ");
Vertex start = k.nextLine();
System.out.println("Enter destination: ");
String destination = k.nextLine();
computePaths(v0);
System.out.println("\nDistance to " + v1 + ": " + v1.minDistance);
List<Vertex> path = getShortestPathTo(v1);
System.out.println("Path: " + path);
The entire code is here:
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;
public Edge[] adjacencies;
public double minDistance = Double.POSITIVE_INFINITY;
public Vertex previous;
public Vertex(String argName) { name = argName; }
public String toString() { return name; }
public int compareTo(Vertex other)
{
return Double.compare(minDistance, other.minDistance);
}
}
class Edge
{
public final Vertex target;
public final double weight;
public Edge(Vertex argTarget, double argWeight)
{ target = argTarget; weight = argWeight; }
}
public class Lab9
{
public static void computePaths(Vertex source)
{
source.minDistance = 0.;
PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
vertexQueue.add(source);
while (!vertexQueue.isEmpty()) {
Vertex u = vertexQueue.poll();
// Visit each edge exiting u
for (Edge e : u.adjacencies)
{
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);
}
}
}
}
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)
{
Vertex v0 = new Vertex("Harrisburg");
Vertex v1 = new Vertex("Baltimore");
Vertex v2 = new Vertex("Washington");
Vertex v3 = new Vertex("Philadelphia");
Vertex v4 = new Vertex("Binghamton");
Vertex v5 = new Vertex("Allentown");
Vertex v6 = new Vertex("New York");
v0.adjacencies = new Edge[]{ new Edge(v1, 79.83),
new Edge(v5, 81.15) };
v1.adjacencies = new Edge[]{ new Edge(v0, 79.75),
new Edge(v2, 39.42),
new Edge(v3, 103.00) };
v2.adjacencies = new Edge[]{ new Edge(v1, 38.65) };
v3.adjacencies = new Edge[]{ new Edge(v1, 102.53),
new Edge(v5, 61.44),
new Edge(v6, 96.79) };
v4.adjacencies = new Edge[]{ new Edge(v5, 133.04) };
v5.adjacencies = new Edge[]{ new Edge(v0, 81.77),
new Edge(v3, 62.05),
new Edge(v4, 134.47),
new Edge(v6, 91.63) };
v6.adjacencies = new Edge[]{ new Edge(v3, 97.24),
new Edge(v5, 87.94) };
Vertex[] vertices = { v0, v1, v2, v3, v4, v5, v6 };
System.out.println("List of Cities:");
for (Vertex v : vertices)
{
System.out.println(v);
}
Scanner k = new Scanner(System.in);
System.out.println("Enter start location: ");
System.out.println("Enter destination: ");
computePaths(v0);
System.out.println("\nDistance to " + v1 + ": " + v1.minDistance);
List<Vertex> path = getShortestPathTo(v1);
System.out.println("Path: " + path);
}
}
System.out.println("List of Cities:");
for (Vertex v : vertices)
{
System.out.println(v);
}
Scanner k = new Scanner(System.in);
System.out.println("\nEnter start location: ");
int start = k.nextInt();
System.out.println("Enter destination: ");
int destination = k.nextInt();
computePaths(vertices[start]);
System.out.println("\nDistance to " + vertices[destination] + ": " + vertices[destination].minDistance);
List<Vertex> path = getShortestPathTo(vertices[destination]);
System.out.println("Path: " + path);
}