Create a Graph class that implements the GraphInterface given you. For Graph<V,E
ID: 3849548 • Letter: C
Question
Create a Graph class that implements the GraphInterface given you. For Graph<V,E>, 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<Town> and Set<Road>. This is the class header:
public class Graph implements GraphInterface<Town, Road>
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 Dijkstra’s 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.List;
public class Town implements Comparable<Town> {
private String Name;
public List<Town> AdjTowns;
//constructor
public Town(String Name, List<Town> 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<Town> getAdjTowns() {
return AdjTowns;
}
public void setAdjTowns(List<Town> 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<Road> {
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 + '}';
}
}
Explanation / Answer
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;
public class Dijkstras_Shortest_Path
{
private int distances[];
private Set<Integer> settled;
private Set<Integer> unsettled;
private int number_of_nodes;
private int adjacencyMatrix[][];
public Dijkstras_Shortest_Path(int number_of_nodes)
{
this.number_of_nodes = number_of_nodes;
distances = new int[number_of_nodes + 1];
settled = new HashSet<Integer>();
unsettled = new HashSet<Integer>();
adjacencyMatrix = new int[number_of_nodes + 1][number_of_nodes + 1];
}
public void dijkstra_algorithm(int adjacency_matrix[][], int source)
{
int evaluationNode;
for (int i = 1; i <= number_of_nodes; i++)
for (int j = 1; j <= number_of_nodes; j++)
adjacencyMatrix[i][j] = adjacency_matrix[i][j];
for (int i = 1; i <= number_of_nodes; i++)
{
distances[i] = Integer.MAX_VALUE;
}
unsettled.add(source);
distances[source] = 0;
while (!unsettled.isEmpty())
{
evaluationNode = getNodeWithMinimumDistanceFromUnsettled();
unsettled.remove(evaluationNode);
settled.add(evaluationNode);
evaluateNeighbours(evaluationNode);
}
}
private int getNodeWithMinimumDistanceFromUnsettled()
{
int min;
int node = 0;
Iterator<Integer> iterator = unsettled.iterator();
node = iterator.next();
min = distances[node];
for (int i = 1; i <= distances.length; i++)
{
if (unsettled.contains(i))
{
if (distances[i] <= min)
{
min = distances[i];
node = i;
}
}
}
return node;
}
private void evaluateNeighbours(int evaluationNode)
{
int edgeDistance = -1;
int newDistance = -1;
for (int destinationNode = 1; destinationNode <= number_of_nodes; destinationNode++)
{
if (!settled.contains(destinationNode))
{
if (adjacencyMatrix[evaluationNode][destinationNode] != Integer.MAX_VALUE)
{
edgeDistance = adjacencyMatrix[evaluationNode][destinationNode];
newDistance = distances[evaluationNode] + edgeDistance;
if (newDistance < distances[destinationNode])
{
distances[destinationNode] = newDistance;
}
unsettled.add(destinationNode);
}
}
}
}
public static void main(String... arg)
{
int adjacency_matrix[][];
int number_of_vertices;
int source = 0, destination = 0;
Scanner scan = new Scanner(System.in);
try
{
System.out.println("Enter the number of vertices");
number_of_vertices = scan.nextInt();
adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];
System.out.println("Enter the Weighted Matrix for the graph");
for (int i = 1; i <= number_of_vertices; i++)
{
for (int j = 1; j <= number_of_vertices; j++)
{
adjacency_matrix[i][j] = scan.nextInt();
if (i == j)
{
adjacency_matrix[i][j] = 0;
continue;
}
if (adjacency_matrix[i][j] == 0)
{
adjacency_matrix[i][j] = Integer.MAX_VALUE;
}
}
}
System.out.println("Enter the source ");
source = scan.nextInt();
System.out.println("Enter the destination ");
destination = scan.nextInt();
Dijkstras_Shortest_Path dijkstrasAlgorithm = new Dijkstras_Shortest_Path(
number_of_vertices);
dijkstrasAlgorithm.dijkstra_algorithm(adjacency_matrix, source);
System.out.println("The Shorted Path from " + source + " to " + destination + " is: ");
for (int i = 1; i <= dijkstrasAlgorithm.distances.length - 1; i++)
{
if (i == destination)
System.out.println(source + " to " + i + " is "
+ dijkstrasAlgorithm.distances[i]);
}
} catch (InputMismatchException inputMismatch)
{
System.out.println("Wrong Input Format");
}
scan.close();
}
}