This is a program implementing the three shortest paths algorithms for directed weighted graphs which are Dijkstra, Bellman-Ford and Floyd-Warshall.
This algorithm finds shortest paths from the source to all other nodes in the graph, producing a shortest path tree. Its time complexity is O(V 2) but can reach less than that when using priority queue. Dijkstra algorithm can’t handle negative weights. But, it is asymptotically the fastest known single-source shortest path algorithm for arbitrary directed graphs with unbounded non-negative weights.
The Bellman-Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted directed graph. It is capable of handling graphs in which some of the edge weights are negative numbers. It works in O(V ∗E) time and O(V) space complexities where V is the number of vertices and E is the number of edges in the graph. It can detect the presence of a negative cycle in the graph.
The Floyd–Warshall algorithm is an algorithm for finding shortest paths in a directed weighted graph with positive or negative edge weights. A single execution of the algorithm will find the lengths of shortest paths between all pairs of vertices. It works in O(V 3) time complexity. It can detect the presence of a negative cycle in the graph.
AGraph input file will contain several lines that describe a directed graph structure as follows. First line contains two integers V and E which determine number of vertices and edges respec tively. This line is followed by E lines describing the edges in the graph. Each of the E lines contain 3 numbers: i, j, w separated by a single space, meaning that there is a weighted edge from vertex i to vertex j (0 ≤ i,j ≤ V −1), and the weight of the edge is w, where w may be negative or positive.
Implement a Graph class that can encapsulate a graph structure and apply
different shortest paths algorithms on it. You need to implement the following methods in this
class:
- Initialize (constructor): Takes a path to graph input file structured as described in section
1.4, reads it and initialize the graph structure.
- Size: Returns the number of nodes in the graph.
- Dijkestra: Takes 3 parameters which are the source node, the costs array and the parents
array. Then applies dijkestra algorithm starting from the source node filling the costs
array with the cost of the shortest path to all other target nodes and the parents array
with the parent of each node in the shortest paths tree.
- Bellman-Ford: Takes 3 parameters which are the source node, the costs array and the
parents array. Then applies bellman-ford algorithm starting from the source node filling
the costs array with the cost of the shortest path to all other target nodes and the parents
array with the parent of each node in the shortest paths tree. Returns False if a negative
cycle is found and True otherwise.
- Floyd-Warshall: Takes 2 parameters which are the costs matrix and the predecessors matrix. Then applies floyd-warshall algorithm filling the costs matrix with the cost of the shortest path between all pairs of nodes and the predecessors matrix with the appropriate values to reconstruct the paths. Returns False if a negative cycle is found and True otherwise.
Implement a command line interface that will enable us to deal with the implemented graph. This interface must take the path of the file describing the graph structure as
an initial input then creates a graph object using it. The interface will be composed of a main
menu and 2 sub-menus which allow the user to apply subsequent operations on the graph from
the following list:
- Finds the shortest paths from source node to all other nodes. You should ask for the
source node and then allow the user to choose 1 of the 3 algorithms to run. Now, the 2
arrays sent to the algorithm are saved and the user can only ask for the cost of the path
to a specific node or the path itself until he decides to exit this operation sub-menu and
return to the main menu.
- Finds the shortest paths between all the pairs of nodes. You should allow the user to
choose 1 of the 3 algorithms to run. Now, all the arrays sent to the algorithm are saved
and the user can only ask for the cost of a path from a specific node to another one or
the path itself until he decides to exit this operation sub-menu and return to the main
menu.
- Check if the graph contains a negative cycle. You should allow the user to choose 1 of
the 2 algorithms to run and show the result.
Provided a set of 15-20 JUnit tests that test the correctness and effeciency of the
different implemented parts. Also, these tests show a comprehensive comparison between
the 3 algorithms w.r.t time factor.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent