Question

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.

For example, a path from New York to Atlanta might be:

New York, Washington, Boston, Los Angeles, Atlanta

Note that the realistic practicality of the path is not a concern for this lab.

However, here’s a caveat. The CitySelector may return null; this denotes that there are no paths

from the current city. When this happens, the CityPathConnector needs to go back to the

previously visited city.

For example, given a source of New York and destination of Atlanta, the first part of the path

might be:

New York, Washington, Boston

If the next city to visit is null, then the path becomes

New York, Washington, Boston, Washington

And the CityPathConnector checks for a next city from Washington (a CitySelector will not

present a city more than once).

From there, the path can be completed; for example:

New York, Washington, Boston, Washington, Charlotte, Atlanta

Or, it will be possible that the CitySelector will return a string of null values, denoting that there

is no path to the destination; for example:

New York, Washington, Boston, Washington, New York (null value and done).

Values of null presented by the CitySelector denote dead-end cities. When this happens on a

path, we will also want to know what the “direct” (for lack of a better term) path is. For example,

if the full path is:

New York, Washington, Boston, Washington, Charlotte, Atlanta

Then the direct path is:

New York, Washington, Charlotte, Atlanta

And when there is no path to the destination, the direct path will be empty. For example (going

from New York to Atlanta):

Full Path: New York, Washington, Boston, Washington, New York

Direct Path: (empty)

Part 1

1. Create an implementation of the CityPathConnector interface.

a. Use the stack data structure (java.lang.Stack) in your implementation.

Part 2

There are three ways to test and validate your implementation, as follows.

1. Use the RandomCitySelector which will present cities or null values in random order. A

null value has equal chance as any eligible city to be presented.

2. Use the ListCitySelector. This allows you to hard code a city order so you can test

specific test cases.

3. Use CityPathConnectorTester. This will automatically run your CityPathConnector

against a series of predefined test cases and will show you which test cases were failed,

if any.

Answer 1

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

Sample output:

Distance to Z: 108.0
Path: [J, K, A, M, R, P, Z]