Homework SourseThis lab is about finding a path from some source city to a
This lab is about finding a path from some source city to a destination city. Cities are
represented by the City enum in the provided jar file. CitySelector is a provided interface that
determines a “next hop” city (the next city to go to). CityPathConnector is a provided interface
that uses a CitySelector to determine a path from a given source city to a given destination city.
Starting from the source city, a CityPathConnector will get the next city to visit from its
CitySelector. The CityPathConnector will repeatedly do this until the CitySelector presents the
destination city, at which point the path is complete. The CityPathConnector needs to keep track
of which intermediary cities were visited.
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
/**
* Selects next cities at random. Keeps tracks of the cities that are
* selected until {@link #reset()} is called.
*
*
*/
public class RandomCitySelector implements CitySelector {
/**
* Tracks the list of selected cities.
* Cleared upon a call to {@link #reset()}.
*/
private List<City> selectedCities;
/**
* Calls {@link #reset()}.
*/
public RandomCitySelector() {
reset();
}
/**
* Resets the list returned by {{@link #getSelectedCities()}.
*/
public void reset() {
selectedCities = new ArrayList<City>();
}
/**
* Returns the list of selected cities since the most recent call to
* {@link #reset()}.
*
* @return list of selected cities.
*/
public List<City> getSelectedCities() {
return selectedCities;
}
/**
* Selects a next city at random. null has an equal chance as any eligible
* city to be returned.
*/
@Override
public City getNextCity(final List<City> pathList) {
City nextCity = null;
while (true) {
Random r = new Random();
int idx = r.nextInt(City.values().length + 1);
if (idx == City.values().length) {
nextCity = null;
break;
}
nextCity = City.values()[idx];
if (!pathList.contains(nextCity)) {
break;
}
}
selectedCities.add(nextCity);
return nextCity;
}
}
***Instructions***
Use the RandomCitySelector which will present cities or null values in random order. null value has equal chance as any eligible city to be presented.
Solution
the java program is written below to find the shortest path between two cities. Here i have defined 11 cities and weighed each path. Stack data structure is made used of. In below program the shortest path between any two cities names as A,D,F,H,J,K,M,O,P,R,Z is calculated using Dikjistra Algorithm. You can change source and destination city in the program, as of now it is given as A to Z.
import java.util.PriorityQueue;
import java.util.Stack;
import java.util.Collections;
import java.util.Scanner;
class Vertex implements Comparable<Vertex>
{
public final String name;
public PathSelector[] 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 PathSelector
{
public final Vertex target;
public final double weight;
public PathSelector(Vertex argTarget, double argWeight)
{ target = argTarget; weight = argWeight; }
}
public class Dijkstra
{
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 (PathSelector 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 Stack<Vertex> getShortestPathTo(Vertex target)
{
Stack<Vertex> path = new Stack<Vertex>();
for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
path.add(vertex);
Collections.reverse(path);
return path;
}
public static void main(String[] args)
{
//Scanner sc = new Scanner(System.in);
//char i = sc.nextChar();
// mark all the vertices
Vertex A = new Vertex(\"A\");
Vertex B = new Vertex(\"B\");
Vertex D = new Vertex(\"D\");
Vertex F = new Vertex(\"F\");
Vertex K = new Vertex(\"K\");
Vertex J = new Vertex(\"J\");
Vertex M = new Vertex(\"M\");
Vertex O = new Vertex(\"O\");
Vertex P = new Vertex(\"P\");
Vertex R = new Vertex(\"R\");
Vertex Z = new Vertex(\"Z\");
// set the edges and weight
A.adjacencies = new PathSelector[]{ new PathSelector(M, 8) };
B.adjacencies = new PathSelector[]{ new PathSelector(D, 11) };
B.adjacencies = new PathSelector[]{ new PathSelector(A, 10) };
D.adjacencies = new PathSelector[]{ new PathSelector(B, 11) };
F.adjacencies = new PathSelector[]{ new PathSelector(K, 23) };
K.adjacencies = new PathSelector[]{ new PathSelector(O, 40) };
K.adjacencies = new PathSelector[]{ new PathSelector(A, 34) };
J.adjacencies = new PathSelector[]{ new PathSelector(K, 25) };
M.adjacencies = new PathSelector[]{ new PathSelector(R, 8) };
O.adjacencies = new PathSelector[]{ new PathSelector(K, 40) };
O.adjacencies = new PathSelector[]{ new PathSelector(B, 40) };
P.adjacencies = new PathSelector[]{ new PathSelector(Z, 18) };
R.adjacencies = new PathSelector[]{ new PathSelector(P, 15) };
Z.adjacencies = new PathSelector[]{ new PathSelector(P, 18) };
computePaths(A); // run Dijkstra
System.out.println(\"Distance to \" + Z + \": \" + Z.minDistance);
Stack<Vertex> path = getShortestPathTo(Z);
System.out.println(\"Path: \" + path);
}
}
