*JAVA*: use Dijkstras Shortest Path algorithm to find the shortest distance between any two towns. Follow the interfaces and the below specifications. Create a class Road that can represent the edges of a Graph of Towns. The class must implement Comparable. The class stores references to the two vertices (Town endpoints), the distance between vertices, and a name, and the traditional methods (constructors, getters/setters, toString, etc.), and a compareTo, which compares two Road objects. Since this is an undirected graph, an edge from A to B is equal to an edge from B to A. This is the class header:

public class Road implements Comparable

TownGraphManagerInterface.java

import java.util.*;

public interface TownGraphManagerInterface {

/**

* Adds a road with 2 towns and a road name

* @param town1 name of town 1 (lastname, firstname)

* @param town2 name of town 2 (lastname, firstname)

* @param roadName name of road

* @return true if the road was added successfully

*/

public boolean addRoad(String town1, String town2, int weight, String roadName);

/**

* Returns the name of the road that both towns are connected through

* @param town1 name of town 1 (lastname, firstname)

* @param town2 name of town 2 (lastname, firstname)

* @return name of road if town 1 and town2 are in the same road, returns null if not

*/

public String getRoad(String town1, String town2);

/**

* Adds a town to the graph

* @param v the town's name (lastname, firstname)

* @return true if the town was successfully added, false if not

*/

public boolean addTown(String v);

/**

* Determines if a town is already in the graph

* @param v the town's name (lastname, firstname)

* @return true if the town is in the graph, false if not

*/

public boolean containsTown(String v);

/**

* Determines if a road is in the graph

* @param town1 name of town 1 (lastname, firstname)

* @param town2 name of town 2 (lastname, firstname)

* @return true if the road is in the graph, false if not

*/

public boolean containsRoadConnection(String town1, String town2);

/**

* Creates an arraylist of all road titles in sorted order by road name

* @return an arraylist of all road titles in sorted order by road name

*/

public ArrayList allRoads();

/**

* Deletes a road from the graph

* @param town1 name of town 1 (lastname, firstname)

* @param town2 name of town 2 (lastname, firstname)

* @param roadName the road name

* @return true if the road was successfully deleted, false if not

*/

public boolean deleteRoadConnection(String town1, String town2, String road);

/**

* Deletes a town from the graph

* @param v name of town (lastname, firstname)

* @return true if the town was successfully deleted, false if not

*/

public boolean deleteTown(String v);

/**

* Creates an arraylist of all towns in alphabetical order (last name, first name)

* @return an arraylist of all towns in alphabetical order (last name, first name)

*/

public ArrayList allTowns();

/**

* Returns the shortest path from town 1 to town 2

* @param town1 name of town 1 (lastname, firstname)

* @param town2 name of town 2 (lastname, firstname)

* @return an Arraylist of roads connecting the two towns together, null if the

* towns have no path to connect them.

*/

public ArrayList getPath(String town1, String town2);

}