Create a Graph class that implements the GraphInterface given you. For Graph, V is the vertex type (a Town), E is the edge type (a Road). You will need to decide how to store the graph, use an adjacent matrix, an adjacency list, or a Set and Set. This is the class header:

public class Graph implements GraphInterface

Within the Graph interface is a method shortestPath, which finds the shortest path from a given Town to all other towns. Since there is a unique shortest path from every vertex to the source, there is a back-pointer to the previous vertex. The method shortestPath then calls dijkstraShortestPath which finds the shortest path from the source to a specific destination. You will be coding the Dijkstras Shortest Path algorithm. You will then be able to find the connections between two towns through the roads that connect them.

You may use the adjacency matrix approach found in the text book, or you may use a set of Towns and a set of Roads. The ShortestPath algorithm typically uses a weighted graph which means that the edges have a weight, and this is used to determine the shortest path. For this implementation, each weight will be the distance of the road in miles.

-----------------------------------------------------------

 import java.util.*; /** * The root interface in the graph hierarchy. A mathematical graph-theory graph * object G(V,E) contains a set V of vertices and a set * E of edges. Each edge e=(v1,v2) in E connects vertex v1 to vertex v2. * * Through generics, a graph can be typed to specific classes for vertices * V and edges E. Such a graph can contain * vertices of type V and all sub-types and Edges of type * E and all sub-types. */ public interface GraphInterface { //~ Methods ---------------------------------------------------------------- /** * Returns an edge connecting source vertex to target vertex if such * vertices and such edge exist in this graph. Otherwise returns * null. If any of the specified vertices is null * returns null * * In undirected graphs, the returned edge may have its source and target * vertices in the opposite order. * * @param sourceVertex source vertex of the edge. * @param destinationVertex target vertex of the edge. * * @return an edge connecting source vertex to target vertex. */ public E getEdge(V sourceVertex, V destinationVertex); /** * Creates a new edge in this graph, going from the source vertex to the * target vertex, and returns the created edge. * * The source and target vertices must already be contained in this * graph. If they are not found in graph IllegalArgumentException is * thrown. * * * @param sourceVertex source vertex of the edge. * @param destinationVertex target vertex of the edge. * @param weight weight of the edge * @param description description for edge * * @return The newly created edge if added to the graph, otherwise null. * * @throws IllegalArgumentException if source or target vertices are not * found in the graph. * @throws NullPointerException if any of the specified vertices is null. */ public E addEdge(V sourceVertex, V destinationVertex, int weight, String description); /** * Adds the specified vertex to this graph if not already present. More * formally, adds the specified vertex, v, to this graph if * this graph contains no vertex u such that * u.equals(v). If this graph already contains such vertex, the call * leaves this graph unchanged and returns false. In combination * with the restriction on constructors, this ensures that graphs never * contain duplicate vertices. * * @param v vertex to be added to this graph. * * @return true if this graph did not already contain the specified * vertex. * * @throws NullPointerException if the specified vertex is null. */ public boolean addVertex(V v); /** * Returns true if and only if this graph contains an edge going * from the source vertex to the target vertex. In undirected graphs the * same result is obtained when source and target are inverted. If any of * the specified vertices does not exist in the graph, or if is * null, returns false. * * @param sourceVertex source vertex of the edge. * @param destinationVertex target vertex of the edge. * * @return true if this graph contains the specified edge. */ public boolean containsEdge(V sourceVertex, V destinationVertex); /** * Returns true if this graph contains the specified vertex. More * formally, returns true if and only if this graph contains a * vertex u such that u.equals(v). If the * specified vertex is null returns false. * * @param v vertex whose presence in this graph is to be tested. * * @return true if this graph contains the specified vertex. */ public boolean containsVertex(V v); /** * Returns a set of the edges contained in this graph. The set is backed by * the graph, so changes to the graph are reflected in the set. If the graph * is modified while an iteration over the set is in progress, the results * of the iteration are undefined. * * * @return a set of the edges contained in this graph. */ public Set edgeSet(); /** * Returns a set of all edges touching the specified vertex (also * referred to as adjacent vertices). If no edges are * touching the specified vertex returns an empty set. * * @param vertex the vertex for which a set of touching edges is to be * returned. * * @return a set of all edges touching the specified vertex. * * @throws IllegalArgumentException if vertex is not found in the graph. * @throws NullPointerException if vertex is null. */ public Set edgesOf(V vertex); /** * Removes an edge going from source vertex to target vertex, if such * vertices and such edge exist in this graph. * * If weight >- 1 it must be checked * If description != null, it must be checked * * Returns the edge if removed * or null otherwise. * * @param sourceVertex source vertex of the edge. * @param destinationVertex target vertex of the edge. * @param weight weight of the edge * @param description description of the edge * * @return The removed edge, or null if no edge removed. */ public E removeEdge(V sourceVertex, V destinationVertex, int weight, String description); /** * Removes the specified vertex from this graph including all its touching * edges if present. More formally, if the graph contains a vertex * u such that u.equals(v), the call removes all edges * that touch u and then removes u itself. If no * such u is found, the call leaves the graph unchanged. * Returns true if the graph contained the specified vertex. (The * graph will not contain the specified vertex once the call returns). * * If the specified vertex is null returns false. * * @param v vertex to be removed from this graph, if present. * * @return true if the graph contained the specified vertex; * false otherwise. */ public boolean removeVertex(V v); /** * Returns a set of the vertices contained in this graph. The set is backed * by the graph, so changes to the graph are reflected in the set. If the * graph is modified while an iteration over the set is in progress, the * results of the iteration are undefined. * * * @return a set view of the vertices contained in this graph. */ public Set vertexSet(); /** * Find the shortest path from the sourceVertex to the destinationVertex * call the dijkstraShortestPath with the sourceVertex * @param sourceVertex starting vertex * @param destinationVertex ending vertex * @return An arraylist of Strings that describe the path from sourceVertex * to destinationVertex */ public ArrayList shortestPath(V sourceVertex, V destinationVertex); /** * Dijkstra's Shortest Path Method. Internal structures are built which * hold the ability to retrieve the path, shortest distance from the * sourceVertex to all the other vertices in the graph, etc. * @param sourceVertex the vertex to find shortest path from * */ public void dijkstraShortestPath(V sourceVertex); } // End Graph.java 

---------------------------------------------------------------------------------------------

import java.util.List;

public class Town implements Comparable {

private String Name;

public List AdjTowns;

//constructor

public Town(String Name, List AdjTowns) {

this.Name = Name;

this.AdjTowns = AdjTowns;

}

//constructor

public Town(String Name) {

this.Name = Name;

}

//getters and setters

public String getName() {

return Name;

}

public void setName(String Name) {

this.Name = Name;

}

public List getAdjTowns() {

return AdjTowns;

}

public void setAdjTowns(List AdjTowns) {

this.AdjTowns = AdjTowns;

}

//method to print the data

@Override

public String toString() {

return "Town{" + "Name=" + Name + ", AdjTowns=" + AdjTowns + '}';

}

//method to compare the data

@Override

public int compareTo(Town o) {

if (this.Name.equals(o.Name)) {

return 1;

} else {

return 0;

}

}

}

----------------------------------------------------------------------------

public class Road implements Comparable {

private Town t1, t2;

private String Name;

private int Distance;

//constructor

public Road(Town t1, Town t2, String Name, int Distance) {

this.t1 = t1;

this.t2 = t2;

this.Name = Name;

this.Distance = Distance;

}

//getters and setters

public Town getT1() {

return t1;

}

public void setT1(Town t1) {

this.t1 = t1;

}

public Town getT2() {

return t2;

}

public void setT2(Town t2) {

this.t2 = t2;

}

public String getName() {

return Name;

}

public void setName(String Name) {

this.Name = Name;

}

public int getDistance() {

return Distance;

}

public void setDistance(int Distance) {

this.Distance = Distance;

}

//method to compare the data

@Override

public int compareTo(Road o) {

if (this.Distance == (o.Distance)) {

return 1;

} else {

return 0;

}

}

//method to print the data

@Override

public String toString() {

return "Road{" + "t1=" + t1 + ", t2=" + t2 + ", Name=" + Name + ", Distance=" + Distance + '}';

}

}