For this assignment, I implemented a weighted graph using their respective interfaces that was provided to me and successfully tested them with tests that I built using JUnit 5.
WGraph_DS
In order to implement the nodes in the graph, I created a nested class which built the nodes and all of its values (key, info, tag) .
To sucessfuly keep track of every node and edge in the graph, I decided to use the HashMap data structure simply because using its "get" and "put" functions allow me to store and pull information in O(1) complexity.
Given the fact that this is a weighted graph and each edge has a weight, I used a multi dimensional HashMap with another HashMap in it as it's value, because that way I was able to quickly store each nodes neighbour (adjacent node) and the weight of their edge.
WGraph_Algo
This class was built in order to properly utilize a couple algorithms in the graph such as finding if the graph is connected, finding the shortest path in the weighted graph, and its distance.
Some of these algorithms I built using the BFS algorithm method in order for traversing and searching throughout the graph, and others I used the Dijkstra algorthim which I also implemented, and using his algorithm I was able to find a weighted graphs shortest path between two nodes.
The purpose of the Dijkstra Algorithm is to find the shortest path between two nodes in a weighted graph, creating a tree of shortest paths from the starting vertex, the source, to all other points in the graph. Therefore using this algorithim, we can find the shortest path between two nodes while taking the weight of each edge in the graph into account.
Here is an example of the Dijkstra Algorithm in action:
Function Name | Time Complexity | Extra Info |
---|---|---|
isConnected | O(|V|+|E|) | The function goes through every node in the graph to find out if it's connected. |
shortestPath | O(|V|*log|V| + |E|) | The function goes through almost every node in the graph to find the shortest path. |
shortestPathDist | O(|V|*log|V| + |E|) | Using shortestPath to find the distance (# of edges it had to cross). |
dijkstra_algo | O(|V|*log|V| + |E|) | Dijkstra algorithm built to find the shortest path between two nodes. |
save | O(|V|+|E|) | Saving a serializable map of the graph on to a file path. |
load | O(|V|+|E|) | Loading a graph from a file path and building it from scratch. |
V - vertices , E - edges
Sources used for help: