Make a graph with ADT with five vertices, one city at each vertex

The 5 cities I will be using are Detroit, Boston, Orlando, Manhattan, Atlantic City

Come up with names of Uber drivers, their location, the distance, their availability, and keep this information in an ADT.

Get the locations of the customer.

Find the nearest driver available in the area.

Assign the customers location to the driver.

Figure out shortest path by using the graph created in step 1 to determine customers start location to their desired destinations.

Print out the distance and cities along the shortest path.

p.s. i need to do above steps using JAVA.

Dijkstra Java code:

//available at http://www.algolist.com/code/java/Dijkstra%27s_algorithm //implements Dijkstra's Shortest Path Algorithm import java.util.PriorityQueue; import java.util.List; import java.util.ArrayList; import java.util.Collections;

/////////////// //Edge class /////////////// class Edge { public final Vertex target; public final double weight; public Edge(Vertex argTarget, double argWeight) { target = argTarget; weight = argWeight; } }

//////////////////////////////////// // Dijkstra's Shortest path class /////////////////////////////////// public class Dijkstra { public static void computePaths(Vertex source) { source.minDistance = 0.; PriorityQueue vertexQueue = new PriorityQueue(); 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 getShortestPathTo(Vertex target) { List path = new ArrayList(); for (Vertex vertex = target; vertex != null; vertex = vertex.previous) path.add(vertex); Collections.reverse(path); return path; }

}//end Dijkstra class

Edge java:

import java.util.PriorityQueue; import java.util.List; import java.util.ArrayList; import java.util.Collections;

/////////////// //Edge class /////////////// class Edge { public final Vertex target; public final double weight; public Edge(Vertex argTarget, double argWeight) { target = argTarget; weight = argWeight; } }

Vertex Java:

import java.util.PriorityQueue; import java.util.List; import java.util.ArrayList; import java.util.Collections;

/////////////// //Vertex class /////////////// class Vertex implements Comparable { 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); } }

Test Shortest Test Path Java:

import java.util.List; import java.util.*;

//your class test shortest path public class TestShortestPath { public static void main(String[] args){ Scanner scan = new Scanner(System.in); String input; int vert; System.out.println("Enter city 1:"); input = scan.nextLine(); Vertex v0 = new Vertex(input); System.out.println("Enter city 2:"); input = scan.nextLine(); Vertex v1 = new Vertex(input); System.out.println("Enter city 3:"); input = scan.nextLine(); Vertex v2 = new Vertex(input); System.out.println("Enter city 4:"); input = scan.nextLine(); Vertex v3 = new Vertex(input); System.out.println("Enter city 5:"); input = scan.nextLine(); Vertex v4 = new Vertex(input); //ask user which vertex to connect to and then distance v0.adjacencies = new Edge[]{ new Edge(v1, 5), new Edge(v2, 10), new Edge(v3, 8) }; v1.adjacencies = new Edge[]{ new Edge(v0, 5), new Edge(v2, 3), new Edge(v4, 7) }; v2.adjacencies = new Edge[]{ new Edge(v0, 10), new Edge(v1, 3) }; v3.adjacencies = new Edge[]{ new Edge(v0, 8), new Edge(v4, 2) }; v4.adjacencies = new Edge[]{ new Edge(v1, 7), new Edge(v3, 2) }; System.out.println("What city would you like to start in? (1, 2, 3, 4, or 5)"); vert = scan.nextInt(); Vertex start = null;//temporary pointer to correct vertex if(vert == 1){ Dijkstra.computePaths(v0); start = v0; } else if(vert == 2){ Dijkstra.computePaths(v1); start = v1; } else if(vert == 3){ Dijkstra.computePaths(v2); start = v2; } else if(vert == 4){ Dijkstra.computePaths(v3); start = v3; } else if(vert == 5){ Dijkstra.computePaths(v4); start = v4; } System.out.println("What city would you like to end in? (1, 2, 3, 4, or 5)"); vert = scan.nextInt(); Vertex end = null;//temporary pointer to correct vertex if(vert == 1){ end = v0; } else if(vert == 2){ end = v1; } else if(vert == 3){ end = v2; } else if(vert == 4){ end = v3; } else if(vert == 5){ end = v4; }

Vertex[] vertices = new Vertex[]{start, end}; System.out.println("Distance to " + vertices[1] + ": " + vertices[1].minDistance); List path = Dijkstra.getShortestPathTo(vertices[1]); System.out.println("Path: " + path); }//end main }//end class