JAVA

PART 1:

Graph.java - This class uses an adjacency matrix as instance variable that can represent any weighted directed graph. It must have a default constructor and a constructor that expects an adjacency matrix as parameter. By default, the adjacency matrix represents the following weight undirected graph:

The Graph class must have all methods in the following class diagram. A description for each method is given below.

Edge.java - This class represents a single edge in the graph consisting of the starting node, end node, and weight of the edge. The Edge must have all methods in the following class diagram.

Below is a description for each of the functions inside the Graph class.

/** * Checks if an edge exists between two nodes

* @param from Start node * @param to End node

* @return true if edge exists, false otherwise

*/

public boolean hasEdge(Integer from, Integer to)

/** * Returns the weight of the specified edge

* @param from Start node

* @param to End node

* @return Weight if edge exists, otherwise 0

*/

public int weight(Integer from, Integer to)

/** * Returns a list of outgoing edges that start at the given node

* @param from Start node

* @return List of edges (may create edges based on adjacency matrix)

*/

public List getOutgoingEdges(Integer from)

/** * Returns a list of all nodes in the graph

* @return List of integers that represent the nodes in the graph

*/

public List getNodes()

/** * Returns a serialized format of the graph, e.g. the adjacency matrix

* @return Serialized graph */

public String toString()

PART 2:

ShorestPath.java - In this part, you will implement the algorithm to find the shortest path in a graph. This class must only have a single method that expects a Graph object, a starting node (Integer), and an end node (Integer) as arguments. The function returns the total weight of the shortest path found between these two nodes.

It requires a HashMap to keep track of computed distances between starting node and every other node (key is node, value is cost).

Use for (Entry row: map.entrySet()) to find the node (row.getKey()) with the lowest cost (row.getValue())

It requires a HashSet to keep track of visited nodes

7 3 5 6 2 8 4 2 2 3 1 7 3 5 6 2 8 4 2 2 3 1